Try executing perl -MCPAN -e 'install CPAN' and then continuing.
Certain older versions of the CPAN toolset were somewhat naive about how to upgrade Perl modules. When a couple of modules got rolled into the core Perl distribution for 5.6.1, CPAN thought that the best way to get those modules up to date was to haul down the Perl distribution itself and build it. Needless to say, this has caused headaches for just about everybody. Upgrading to a newer version of CPAN with the commandline above should fix things.