Il problema è che gli header vanno messi primi di qualsiasi istruzione di output, potresti risolvere il problema bufferizzando la pagina

http://it2.php.net/manual/it/function.ob-start.php

vedi anche

http://it2.php.net/manual/it/function.header.php

Ciao