Salvador, verás, la funcion
header(), sirve para modificar las cabeceras de la página. En las cabeceras de la página puede venir diversa información, como que el documento puede ser texto, una imagen png, una imagen gif o simplemente la longitud del documento.
Al imprimir el texto, sin antes enviar cabeceras, automáticamente ese documento pasa a ser de texto, por lo que al enviar las cabeceras, una vez escrito algun texto, dará error.
Aún si modificas el codigo, poniendo la función header() al principio del codigo, el resto del código (creo, corrijanme si me equivoco) no se ejecutaría.
La solución está en redirigirlo mediante HTML. Como bien te dio la solución jdarkname, consiste en introducir el siguiente código:
Donde el "2", pon los segundos que quieres esperar para redireccionar al cliente y donde "destino.php" la página a la que quieres enviar al usuario.
Cita:
Iniciado por jdarkname 
Código HTML:
<meta http-equiv = refresh content ="2; url=destino.php">
Un saludo