Esto es un error común al utilizar la función header. Fijate lo que dice la
documentación de php.net al respecto:
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.
Saludos.