What you should do is download and try to install a Perl module from CPAN without using the CPAN shell. Test-Simple is a good example because it has almost no dependencies and doesn't do anything fancy.

Download it. Unpack it. perl Makefile.PL. make. make test. sudo make install.

If that doesn't work then at least you'll have all the error messages you need. If it does work your CPAN shell is misconfigured. Talk to the Ubuntu folks. Or the CPAN shell folks. This isn't about MakeMaker.