ehm il session_start(); va messo in ogni pagina altrimenti è ovvio che ti perde la sessione. Se da pagina A vai a pagina B, entrambe le pagine devono iniziare con session_start().
Se queste pagine presentano delle inclusioni, lì non metterlo. E ara quello spazio prima del <?php come fa notare satifal.