La función header es un tanto delicada...
Cita: Recuerde que la función header() debe ser llamada antes de que cualquier salida sea enviada, ya sea mediante etiquetas HTML normales, líneas en blanco de un archivo, o desde PHP. Es un error bastante común interpretar código extra con include(), require(), o alguna otra función de acceso de archivos, y terminar con espacios o líneas en blanco que son impresas antes de un llamado a header(). El mismo problema existe cuando se usa un archivo PHP/HTML único.
Ojo con cualquier espacio en blanco.
Saludos.