Your web server configuration may not yet know what to do with cgi files.

Are "Options +ExecCGI", "ScriptAlias'", " AddHandler cgi-script cgi pl", and maybe "UserDir" set? The apache httpd manual has details of how to choose sane settings for those.

(Added) Come to think of it, the "Premature end of script headers" message indicates that httpd is trying to treat your script correctly, so ignore the above. By chance are you uploading the script from a winders box? If so you may have a bogus \r tacked onto the perl path in the splatline. Insert a space and a comment or something to check that.