If you can run it from the command line, have you consired switching to the user that Apache is running under? If that fails, it may very well be some sort of permissions problem. Also, check to see if you have more than one version of Perl on the box and if you are running the same version of Perl from the command line as from the CGI program. I've been bitten by the latter.
Cheers,
Ovid
New address of my CGI Course.
Silence is Evil (feel free to copy and distribute widely - note copyright text)