I have a RHEL3AS box here with Apache on it, never had any problem with CGI. I also use perl5.8.6 installed elsewhere. No problem with that, either.

So I suppose the big question to me is ... are you running apache in a chroot jail? What user is apache running as - does that user somehow not have access to read some of these directories?

Update: I highly doubt that kyoshu's advice will help, given the OP's description, but I will grant that it's really easy to try (at least the symlink part).