headerを呼ぶ前に何かしらの文字列が出力されているとか、
http://php.net/manual/ja/function.header.php
PHPスクリプトの最後「?>」で閉じた後、改行を2個入れているとか、
http://ameblo.jp/katyos/entry-10343144731.html
どうでしょうか。