Well first questions I have are:

1. What is the content of your @INC?
2. Where have you installed your modules?

With these two most crucial pieces of information we should be able to figure out where the problem is.

In CGI environments that I've worked on before all the modules are "rooted" in the cgi-bin that the CGI scripts are running from.