Your code looks OK to me, and indeed works on my Web server. Is that the entire script? And is it run as a standard CGI script (not mod_perl, nph, etc.)?
Two useful debugging tools are to run the script by hand to see exactly what it's printing, and getting the URL where your script resides with a command-line tool, like wget or lwp-request from LWP.
philcrow suggests that you use CGI's redirect method, but that actually just prints a Status and Location header, just as your script does. Still, this module is more likely to work under mod_perl and the like, and might be worth a try, if nothing else to verify that it's behavior is identical to your script.
