What are the values of the environment variables PERL5LIB and PERLLIB? They tell perl where to search for modules. Does running cpan without using sudo give the same error? If not then check your /etc/sudoers file.