It could also be a problem with file ownership / permissions. If the user that is running the web server, and thus the CGI's doesnt have permission to read the require'd libraries, you will get that exact error. For instance, i ran a trivial test where i changed a librarys owner and group to root, with a 600 permission, then tried to require it in another script, and got the cant locate library in @INC error. Heres what i mean:

ls -l test_lib.pl
-rw-------    1 root     root           62 Oct  7 11:30 test_lib.pl

# and heres the script that includes it:
#!/usr/bin/perl

require 'test_lib.pl';
[download]

Yep, thats the whole thing.

So you may want to look at permissions, ownership of your required files.