If you're seeing the headers when you print them, then something is getting printed ahead of them. If your script isn't doing it, it's possible that your web server is sending something ahead of what your CGI script prints.

Try fetching the page with a utility like wget, so you can see exactly what's being output. Another option is to talk directly to the HTTP server with telnet, entering a GET command and the Host header like below, followed by a blank line. That'll let you see exactly what your browser sees (assuming your server doesn't do any funny browser-header-specific stuff), with all headers first and then the text of the page.

$ telnet my.server.com 80
Trying....
Connected to....
Escape character is '^]'.
GET /cgi-bin/myscript.cgi HTTP/1.1
Host: my.server.com

# output will come here
[download]