I was using the libmoose-perl package of ubuntu 7.10. It turned out to be Moose 0.21.
I wouldn't have thought that they were that far behind, so I didn't check versions before.
Sorry, my fault. It works like a charm now with 0.40.
Thanks for your help!
For future reference, (and hoping Ubuntu works the same as Debian):
When a CPAN module is out of date on Debian, or not available, I use dh-make-perl <module-name> to create my own package and install it with dpkg or apt-get. Mostly it works great, and has the advantage that if the Debian maintainer updates their package, apt-get (or whatever) will do the right thing.