Can you run some perl scripts in there from the shell and report back to us what occurs? Do they execute without errors?
(type perl SCRIPTNAME.cgi)
Or, what's in your /usr/local/apache/logs/error_log, when a script is running and failing?
that will probably help the most in determining the source of the issue.