Eso me suena a error en la función header que estás utilizando. Échale un ojo a http://brak.unsl.edu.ar/php/function.header.html.
Especialemente a esta oración:
Cita: Nota: Recuerde que la función header() debe llamarse antes de que se genere salida alguna, bien con etiquetas HTML normales o con PHP
Suerte!