A couple of questions.
1) Do other scripts work properly? Find an example 'test.cgi' script and see if you can get it to work. Here's a really simple one:
print "Content-type: text/html\n\n";
chmod +x this, and see if you can get it to say "Hello!" in a browser.
2) Make sure your permissions are right. I know you already did this, but do it again. :>
3) (this kind of goes along with #1) Login to the panel and make sure that your domain has full CGI enabled (and set to run as the same user that owns the file).
4) Are you editing the script on a Windows machine? The second leading cause of internal server errors (behind permissions problems) is when scripts have DOS carriage returns in them. You can use dos2unix to strip these, or simply open the file in pico and save it (^O).
5) Does the script execute from the command line (./script)?
6) Check your logs and see what kind of error you're getting.