Try to debug your headers.
Even if you print the headers the right way, there's still the possibility your web server (apache?) prints some headers.
I'm using firebug (www.getfirebug.com),
but you could also telnet to your webserver.

telnet localhost 80
GET /theurl
[download]

I'm also using mod_rewrite with apache.
This way you can, e.g., "redirect" all urls beginning with http://www.yourserver/download/ to your cgi script.

If you put out pdf files, for example, the adobe reader will not recognize the correct filename otherwise, the button "save a copy" would save the file as "cgiscript.pl".