Gli header devono essere PRIMA di qualsiasi output html...

Hai provato a metterlo in cima al codice, come prima cosa?