I had the same problem yesterday (Debian). I had no time to investigate and just did a force install CPAN.

This solved it for me :)