В PHP MANUAL написано:
Remember that header() must be called before any actual output is sent, either by normal HTML tags blank lines in a file, or from PHP.
Это относится и к инклуде(), в котором есть ХТМЛ, и к пробелам и пустым строкам до РНРшных скобок, в которых вызываешь header().