I seem to remember having this problem. moritz is right to point you to the package. I think it's generally a good idea to stick with the Ubuntu packages whenever the needed module (and needed version of the module) is packaged. http://packages.ubuntu.com/search?suite=hardy&keywords=hardy
Not sure if this is related to the reason you're asking, butI did have a problem installing modules via CPAN on Ubuntu 8.04. It would always fail when trying to fetch with LWP. It would take forever to install anything via CPAN. However, I finally realized I didn't have NcFTP installed.
sudo apt-get install ncftp
After that, it was just a matter of setting the paths for ncftp and ncftpget in config file.
cpan > o conf ncftp /usr/bin/ncftp
cpan > o conf ncftpget /usr/bin/ncftpget
Still don't know why LWP was failing, but I've moved and life has been more pleasurable since.