Could it be that there is anything in your file before your opening "<?php" tag? Anything at all? a space, a newline?
If there is, then you won't be able to redirect.
I've you have, say, a space before the opening PHP tag, then this space will be sent down to the client's browser. The server will assume the space is the start of a text document and will automaticallty send the appropriate headers for that before moving onto the actual content - the space.
If you then try to send a header (in your case, a redirection header), this introduces a problem, as the server has now told the client that all the headers have been sent and all that follows is content. Not wishing to break protocol and possibly bring about the The End of The Internet, your server refuses to send the header out of sequence.
If your server is set up to display errors and warnings, it would display a message saying something like "Unable to send header" at this point. Otherwise it may just silently stop.
So, check for anything at all before the opening php tag, and get rid of it.