Are you in fact using the same Perl executable for both command line and CGI? If not, that would explain your problems. The @INC looks like a system Perl, which would not normally look for modules in your personal directory.

If you are using the system Perl, you should use the system's package manager to install modules. Using the cpan client (or its variants) can cause considerable grief, as I have learned from sad experience, and as you may be learning now. If there is no package for this module, you should probably custom-build your own Perl, and that's not a bad idea anyway, as the previous responder pointed out.

If you are using a custom-built Perl, did you install it in a system-wide directory and then take the local::lib installer option when you initialized CPAN? You want the sudo option in this case.