Hmmm pues no sé que te sale mal yo lo he hecho tal como te dije y me funciona. Y tengo como 3 o 4 includes en algunas de mis paginas y en cada una un session_start() y me funciona bien. Prueba lo siguiente, quita del header.php el session_start() y añadelo al comienzo de cada página así. Deberia funcionarte...