If you run your CGI script from the command line, as in perl -w my_cgi_script.pl, do you still get an error?

The advantage of running the script from the command line is that you often get a more descriptive error message, including line number where the error occurred.

I would say that ninety-nine percent of the time I get the premature-end-of-header CGI error the problem has nothing to do with CGI and the script won't run from the command line either.