This could be caused by one of two things:
You have two versions of Perl on your machine. You are installing modules into one, and Bugzilla is using the other. Rerun the CPAN commands (or manual compile) using the full path to Perl from the top of checksetup.pl. This will make sure you are installing the modules in the right place.
The permissions on your library directories are set incorrectly. They must, at the very least, be readable by the webserver user or group. It is recommended that they be world readable.