Check the environment your CGI programs run under. Generally, if you are running apache, the user:group is nobody:nobody. As a test, print out the contents of your %ENV hash from a cgi program - maybe the PATH is different, and it cannot find your perl binary?