Può essere che session_start() non avvii correttamente la sessione (in una qualsiasi delle due pagine), ma se non ottieni nessun altro errore (avendo abilitato la visualizzazione di tutti i livelli di errore) a parte quello che hai citato, allora non è questo. Comunque verificarlo. (http://php.net/manual/it/function.session-status.php)
Ipotesi: può essere che sia un problema di cookie. Magari ti stai portando dietro una vecchia sessione, (magari per un problema del browser, a volte capita) hai provato a cancellarli?