Perhaps it's multiple Perl versions installed? Try this simple CGI script:

#!/usr/bin/env perl
use warnings;
use strict;
use Config;
print "Content-type: text/plain\n\n";
print "This is Perl ".sprintf("v%vd",$^V)." at $^X, ",
    "perlpath=\"$Config{perlpath}\", prefix=\"$Config{prefix}\"\n";
print "INC: $_\n" for @INC;
[download]

Note that it may make a difference whether the first line is #!/usr/bin/env perl (whichever perl is in the PATH) or #!/usr/bin/perl (that specific perl).

Also maybe check the permissions on the paths in @INC?