There's some good info above for why things go wrong. And trouble shooting advice from the command line. But CGIs often behave very differently from the command line b/c of permissions or even paths.
in reply to Premature End of Script Headers Reasons?
My favorite trouble shooting tool is use CGI::Carp like so use CGI::Carp qw(fatalsToBrowser); Usually, that will identify the problem to you immediately (you can always check your error logs too depending on how they're configured but I like the module better).
Do not add this into a production script. It can give away functional details about the CGI or your system to potentially malicious users. You could copy the CGI to a new name (and path?) and set it to only accept a particular user or local connection and then add it. Then just run it till it dies and spits out the reason and not just a generic 500. Make sure you have good error catching routines in your script too to ensure the best information in the die'ing.