404 Error on a file that exists

A script makes a GET request to my URL like so:

http://mydomain.com/cgi-bin/uu_ini_status_audios.pl?tmp_sid=b742be1d131c4d32237a9f1fcdca659e&rnd_id=0.2363453360320319

However, I get a 404 returned straight away:

The requested URL /cgi-bin/uu_ini_status_audios.pl was not found on this server.

But that script exists on my server, I can see the file! It has the correct permissions (I gave it a 777 to be sure). It is also owned by my apache user and its in the group apache.

What am I missing??

Thanks for any help on this!

Update

I thought it would have been a htaccess (rewrite) but I don't think it is anymore. I tried putting a index.php file in there and try to access it via my URL but I can't even do that! I tried this:

http://mydoamin.com/cgi-bin/index.php – same 404 error! I get this in myerror log:

[Tue Sep 14 14:42:49 2010] [error] [client xx.xxx.xx.xxx] script not found or unable to stat: /var/www/vhosts/mydomain.com/cgi-bin

Access_log file:

xx.xxx.xx.xxx – – [14/Sep/2010:14:48:25 +0200] "GET
/cgi-bin/index.php HTTP/1.1" 404 475
"-" "Mozilla/5.0 (Windows; U; Windows
NT 6.0; en-US; rv:1.9.2.9)
Gecko/20100824 Firefox/3.6.9 (.NET CLR
3.5.30729)"

Update 2

My htaccess file:

<IfModule mod_rewrite.c>
RewriteEngine On
RewriteRule ^blog/ - [L]
RewriteCond %{HTTP_HOST} ^www\.mydomain\.com$ [NC]
RewriteRule ^(.*)$ http://mydomain.com/$1 [R=301,L]
RewriteRule ^search/(.*)/(.*)/(.*)/(.*) /search.php?searchfor=$1&sortby=$2&page=$3&searchterm=$4
RewriteRule ^confirmemail/(.*) /confirmemail.php?code=$1
RewriteRule ^resetpassword/(.*) /resetpassword.php?code=$1
RewriteRule ^resendconfirmation/(.*) /resendconfirmation.php?userid=$1
RewriteRule ^categories/ /categories.php
RewriteRule ^([-_~*a-zA-Z0-9]+)(\/)?$ /memberprofile.php?username=$1
RewriteRule ^browse/audios/(.*)/(.*)/(.*)/(.*) /audios.php?sortby=$1&filter=$2&page=$3&title=$4
RewriteRule ^browse/categories/audios/(.*)/(.*)/(.*)/(.*) /categoryaudios.php?sortby=$1&filter=$2&page=$3&title=$4
RewriteRule ^audios/(.*)/(.*) /playaudio.php?audioid=$1&title=$2
RewriteRule ^download/audio/(.*)/(.*) /downloadaudio.php?AUDIOID=$1&title=$2
RewriteRule ^members/audios/(.*)/(.*) /memberaudios.php?pid=$1&username=$2
RewriteRule ^syndicate/audios/(.*)/(.*) /syndicateaudios.php?filter=$1&title=$2
</IfModule>

Update 3

[root@smydomain ~]# ls -la /var/www/vhosts/mydoamin.com/httpdocs/cgi-bin/
total 60
drwxr-xr-x  3 apache root     4096 Sep 14 14:37 .
drwxr-x--- 20 som    psaserv  4096 Sep 14 14:40 ..
drwxr-xr-x  2 apache root     4096 Sep  7 03:01 configs
-rwxrwxrwx  1 apache root        4 Sep 14 14:37 index.php
-rwxrwxrwx  1 apache apache   6520 Sep  7 03:01 uu_ini_status_audios.pl
-rwxr-xr-x  1 apache root     3215 Sep  7 03:01 uu_lib_audios.pl
-rwxr-xr-x  1 apache root    30249 Sep  7 03:01 uu_upload_audios.pl