Have you looked at your web servers error logs to get the more specific error message? Have you tried adding:

use CGI::Carp qw(fatalsToBrowser);
[download]

to the beginning of your script? Have you tried running your script from the command line to see the error it gives you there? The generic "premature headers" usually indicates a very basic problem with the script (it's dieing because of a syntax error or something similar). Posting the code that doesn't work would help us out in determining what the problem is.

--Brian