(Mainly for the benefit of those that wouldn't know where to start looking for solving this problem):

This boils down to basic CGI debugging. Whenever you get a server error pointing to a lack of headers, that's your first indication that your script either did not compile correctly (errors in the error logs), or it compiled and executed, but spat out content without correct/any headers. The very first thing you check is to be sure each path through your script ends up giving us HTTP headers first.

In addition, since you're using CGI.pm, you can run your script on the command line and pass your arguments straight to it. This is an excellent way to test form submissions without the added complexity of a web server. Frequently this helps you identify CGI-related problems.