No puedes hacer un redireccionamiento por HTTP después de que has enviado alguna cabecera...
me explico, para crear una sesión, haces el llamado a session_start(), con lo que ya estas enviando una cabecera HTTP; posteriormente haces un llamado a header(), que envía otra cabecera HTTP, y eso es lo que te está penalizando el PHP.
Te puedo sugerir 2 cosas:
1. Utiliza redireccionamiento por HTML (con los tag <META> dentro de <HEAD>, en el momento no recuerdo como hacerlo) en vez de hacerlo con header();
2. Redireccionar a un HTML (index.htm) puede hacerte perder las variables de sesión.