I just had a similar problem myself and found out the problem was linked to two installations of Perl on the same machine, in different directories, with different @INC. The @INC from the command line and the @INC from the CGI were different, and voila. The key is to go to /usr/bin/ (or wherever your main installation is) and do a
./perl -MCPAN -e shell to make sure the modules are installed in the proper @INC. (Of course, you could always just move the modules around manually, but I prefer the easy way. :-D)
Gary Blackburn
Trained Killer