l'header lo devi mettere prima di qualsiasi forma di output, altrimenti entra in conflitto con gli header, puoi però anteporre un ob_start(); da mettere all'inizio dello script.

In alternativa per fare il reindirizzamento puoi usare anche un meta html:
codice:
<meta http-equiv="refresh" content="2; url=tua_pagina.php" />
2 sono i secondi prima del reindirizzamento.