That's great and all, but the important part is when the CGI script is outputting the headers. Obviously it has to be the first output or its not going to work. You could be using some module or other that is has a function being called first before any code you are writing.
Generally you can test a CGI script from the command line in shell:
prompt: perl /home/username/domain/script.pl
And if using the CGI module, it might ask for paramters; just hit enter if you don't wish to enter any. The next output from the script should be the headers you're expecting (unless your script requires the CGI environment).
You might also try using something like:
# output this at compile time
print "Content-Type: text/html\n\n";
To see if that makes the script output that as the headers.
Also, are you attempting to use Unicode or a character set that uses other than low ASCII?
Perl / MySQL / HTML CSS