the shebang line is hopefully the first line in your script ? it has to be.....no spaces before....nothing...
also try not to print the HTTP header, but use the following line:
use CGI qw(:standard);
if that still doesnt work, look at the apache error logs, they contain the most usefull infos what went wrong ^^