apache 2.2 - 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:

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

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

Answer

SuExec was causing the problem for me.

Disabling this means my scripts in the cgi-bin can run. But you must make sure the directory and the scripts have the same permissions i.e. 0755. In addition, the directory and the scripts must be owned by the same person.

These were the requirements to get my scripts working! I hope this helps someone.