Potrebbe dipendere tutto da un rimando a capo inserito prima del tag di apertura del php!
Qualsiasi cosa al di fuori di tali tag viene inviato al browser, controlla quindi che il file inizi con <?php senza che prima ci siano spazi o rimandi a capo.

Questo vale ovviamente anche se il file che contiene session_start() viene incluso da altre pagine. Tutto quello che c'è prima dell'inclusione è come se fosse inserito nello stesso file prima di session_start();