It might not be a case of permission but ownership. When running CGI the script has to be run as your user and if this "switch user" operation isn't done you will have permission denied problems. I only bring this up because it happened recently for one of my domains and support had to rebuild the server configuration and restart it.
Here is a perl script you can use to check:
my $username = getpwuid($>);
print "content-type: text/plain\n\nrunning as $username\n";
If it says 'running as dhapache', your CGI script is running as the web server and not as your user.
Perl / MySQL / HTML+CSS