I'd have to see the page in action without the exit(), but generally once you output a Location redirect via HTTP headers, you don't really want anything else outputted.
It could be that the script is outputting something later on and is killing the redirect. Again, without a link to this page without the exit(), I can't tell you much more.
EDIT: Also, if you'll look in the manual for [man]header/man, you'll see that even the person who wrote that manual page used an [man]exit[/man] call after the Location redirect examples.