You might want to check the permissions on the cgi directory. Since you are root, it may be the case that root owns the directory and the nobody user can't access it. You may try to su nobody and see if he had permissions to execute the script in that directory. I'm not sure if the nobody user needs execute permission on that dir.
The way that I usually setup directories for my virtual servers is to setup a directory, in my case under /home/apache and recursivly set the permission on that dir to nobody.nogroup and point the virtual server to that directory.
As for cgi-bin directories, I usually don't use them. Some say it is a security hazzard, but it is easier to do the following.
This enables cgi programs to execute in the directories.
Hope this helps