el problema es que ya imprimiste datos en pantalla, asi no podes poner un header, tenes que ponerlo alprincipio del codigo, pero no imprimirias nada, asi que imprimi y en vez de pone header ponelo en html con un "<META REFRESH
No es necesario que
header() este al princio (eso es para
session_start() para evitar Warnings), pero no podes printar nada en l aweb antes de usar un header().
Si tu codigo necesita usar un header en determinados lugares, lo que te recomiendo hacer es que no imprimas nada a vuelo, sino que gaurdes todo lo que quieras mostrar en tu web en una variable, y asi podes usar header("Location: loquesea.php") donde quieras, y por ultimo pasas a imprimir la variable.
saludos