Verifique se todos os seus arquivos estão salvos com a codificação UTF-8. Os arquivos codificados em UTF-8 podem incluir uma BOM (Byte Order Mark) para informar a diferença entre a ordem big-endian / little endian byte. O PHP não entende a BOM e, quando ela acerta no começo do arquivo, supõe que ele está lidando com dados e envia-os - então já é tarde demais para modificar cabeçalhos.
A solução seria ter certeza de salvar seus arquivos como ANSI - configure seu IDE / editor
Espero que ajude.
EDITAR:
Se este for o caso, você provavelmente tem muitos arquivos que você precisa converter. Você pode usar tente usar este código de shell bash que usa iconv para fazer isso para você (adaptado de: link )
for files in /mydisk/myfolder/*.php
do
iconv -f UTF-8 -t ISO-8859-1 "$files" "${files%.php}"
done