This is for future reference.
If you are getting a 500 internal server error for your cgi-bin, have all the permissions set right and are using Plesk (or any other suexec virtual apache platform) the following command might be your answer.
SSH in and type the following:
chown root:apache /usr/sbin/suexec
That should resolve most of the uid/gid mismatch issues and the 500 internal server issues. The technical explanation is that suexec runs the calling program as the owner/group that the suexec program is saved under and apache will run most scripts with a suexec (in a virtual server environment) to sanity check script execution and prevent malicious scripters. Plesk will sometimes save this file under the wrong credentials. Thus the headaches.