Ahem, quite obvious suggestion but nevertheless - 99% of time if a module is found by  perl -MMod::Name but is not found by, for example, a CGI script that is because you have different environment in the console and in the script. Try checking $ENV{PERL5LIB} to see the difference, maybe you have some part of CPAN library installed locally for your user or something.

As a side note - have you seen those Makefile.PL files in CPAN distributions? Maybe you are re-inventing the bike here, why not use a standard solution for the problem?