Ya te dije que session_start va al inicio del archivo, linea 1.
El problema de header es bastante comun,
http://www.php.net/manual/es/function.header.php
cita:
Recuerde que header() debe ser llamado antes de mostrar nada por pantalla, etiquetas HTML, líneas en blanco desde un fichero o desde PHP. Es un error muy común leer código con funciones como include o require, u otro tipo de funciones de acceso de ficheros que incluyen espacios o líneas en blanco que se muestran antes de llamar a la función header(). Sucede el mismo problema cuando se utiliza un solo fichero PHP/HTML.