... ese problema es muy común y se ha tratado por demás en el foro... por favor antes consulta las FAQ y usa el buscador del foro.
El problema es que antes de usar la función header() tienes algún tipo de salida al navegador...
header():
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.
Tendrás que reordenar tu código para evitar esto (ve que ni sentido tiene entregar algo si vaz a redireccionar al fin y al cabo).
Suerte!