I've placed this file in both public_html and as a test in public_html/ cgi-bin directories in my local user account (I dont have root access - its a corparate network). The file definitely has read and execute permission (744) as have the assoicated directories.
My guess would be the permissions are awry -- if I parse that correctly, 744 is -rwxr--r-- which means that other users (such as the user your server runs as, likely "www" or "wwwdata"?) can't execute the shell-script. As a first pass, I'd ensure that the file has permissions, and the directory can be scanned by the webserver ("eXecute" permissions on the containing directory):
bash$ cd ~/public_html/cgi-bin bash$ chmod go+rx test.py .
As a test I tried a perl cgi hello world test, and this worked correctly.
If the perl script is working correctly, I suspect the directory permissions are set correctly, so I'd compare permission of the .pl vs. the .py scripts to see if they're the same. Alternatively, if your server is running mod_perl, it might be short circuiting the CGI aspect, detecting the .pl file & running it, and thus might be a red herring. (not using perl/mod_perl, I don't know the ins and outs of this, so I could be waaaaay off base on this line of thinking)
Just my first-pass debugging thoughts, -tkc -- http://mail.python.org/mailman/listinfo/python-list
