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:
Yep, thats the whole thing.
So you may want to look at permissions, ownership of your required files.