Questo problema fece impazzire anche me qualche anno fa.
Dipende dal fatto che prima della funzione header() il tuo script sicuramente invia qualcosa a video tramite le funzioni echo, print ecc..., quindi gli headers secondo il parser ( e di fatto ) risulterebbero già inviati.
Io sono sempre riuscito a risolverlo cosi', nella prima riga del codice della pagina in questione inserisci questa funzione:

Codice PHP:
ob_start(); 
Non dovrebbe esserci più alcun problema e tutto dovrebbe funzionare.
Facci sapere.
Ciao