I just came across this same problem and as often seems to be the case, PerlMonks had the answer.

I had a directory called /Library/Perl/Updates/5.8.8 that contained the same readme file as mentioned above. I renamed it to 5.8.8_old, ran CPAN again and modules installed without issue.

I'm thinking that maybe the problem arises when the machine has been upgraded or restored from an old disk image (Time Machine).

Short version: +1 for try deleting or renaming anything in /Library/Perl/Updates/.

Thanks Monks.