Atha acuerdate que si envias algo al navegador de la persona antes de header() va a ver un error. Mira para que veas lo que dice
php.net
empezando la oracion dice y cito directo
Cita: Remember that header() must be called before any actual output is sent, either by normal HTML tags, blank lines in a file, or from PHP