It's because the web server is waiting for more output from your script before it honors the redirect. You have to tell the web server you're done with output. One way would be to close STDOUT:

print CGI->redirect(...);
close STDOUT;
[download]

Another is to set your buffers to autoflush and send an End-Of-Transmission character:

$|=1;
print CGI->redirect(...);
print chr(4); # EOT
[download]

I've never actually had to do something like this, so others might have a more elegant solution.