L'unica cosa che mi viene in mente è che la funzione header() va invocata prime che sia prodotto dell'output... sia esso anche solo uno spazio bianco.

ad esempio se nel tuo file hai la prima riga vuota perchè hai premuto un invio e poi hai iniziato con <?php... , stai producendo dell'output HTML che dal punto di vista del browser non produce nulla, ma dal punto di vista di PHP non ti permette di aggiungere ulteriori header all'output con la funzione header(), perchè gli header sono stati già inviati al browser non appena è iniziato l'output HTML.