Could be the permissions on the file; the web user will have to have execute permissions. Can other scripts in the cgi-bin directory execute? If not, the permissions on the directory could be incorrect, or the ScriptAlias directive is not set up correctly or something along those lines.
The error_log (Apache, right?) will hopefully offer some useful information (something more useful than 'premature end of script headers'
).