I'm not sure what do you mean by "does not work" for what I can see the code is correct, but I would consider doing few things to try it on...
First, if a page that you would want to redirect user to is on the same site as the one that you are redirecting from I woul advise you to use relative paths i.e. if a page you are trying to redirect to two folders above the page you are redirecting from use:
header("Location:../../page.php");
Second, for I don't know what reason I have to add exit statement after header to make it work because if I don't sometimes it will not work. I.E.
header("Location:path/to/page.php");
exit();
Also, I would like to hear are you certain that the code reaches the header directive? What I mean is that it could die on either of the two places where it could (after connection to database or after INSERT statement) without you knowing it (error displaying is turned off or whatever).
At last if you are certain that the header statement is reached - what do you get as a result? A blank page or what?
At the end I will say again: your code does look O.K. to me, but I could be wrong... ๐