Te cito un párrafo de php.net con los errores mas comunes del uso de esta función, y fijate si la mano viene por ahí:
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.
Fijate no haber dejado espacios en blanco o saltos de linea antes de "<?", y también fijate que tampoco las haya después de los "?>" que tenes en los includes.
Saludos.
PD: la próxima vez por favor encerrá el código PHP entre las etiquetas del foro correspondientes, para hacer su lectura mas cómoda.