Sorry for the late reply. Actually almut has the probable cause of your problems. Especially after all my suggestions turned up negative.

EDIT: A step-by-step recipe of almuts solution:

First find the installed ExtUtils::AutoInstall:

locate ExtUtils/AutoInstall
[download]

or

find /usr/lib -name 'AutoInstall.pm' -print
[download]

This will tell you the location of AutoInstall.pm, probably in /usr/lib/perl5/5.8.0/ExtUtils/

Now copy the systemwide AutoInstall.pm to your homedir:

mkdir ~/lib/perl5/site_perl/5.8.0/ExtUtils 
cp <pathtoautoinstall>/AutoInstall.pm ~/lib/perl5/site_perl/5.8.0/ExtU
+tils
[download]

Edit your copy of AutoInstall.pm. Find the line mentioned by almut (the one with Config{sitelib}) and change it to the newer version.

That's it. You don't need to change PERL5LIB because you already did this when you installed cpan with Zaxos method.