The regular @INC and mod_perl's @INC often differ slightly. Try:

warn "\@INC is: ", join ( ', ', @INC );
[download]

in both your normal .pl and from the failing CGI. If this is the problem put a use lib '/your/path/here'; into a script and then call it with PerlRequire.

Another thought: is your apache chrooted in any way?

Yet another thought: Check the permissions.