It is the exact same root cause: both header() and session_start() (as well as setcookie()) add HTTP headers to the queue of headers that will be sent as soon as any "real" output is sent. Therefore they will fail if called after any such output has been generated.
So something is causing output to be generated before your call to header(). This can be something as simple as a newline or space before your opening <?php tag. A bit more insidious is if you edited the file with an editor that saved it as UTF-8 or some other Unicode character set and included the Byte Order Mark (BOM) at the start of the file. If this could be the case, make sure that your editor is either saving the file as plain ASCII text, or else UTF-8 with no BOM.
Another "gotcha" can be if the main script includes another PHP file before one of these header functions, and that file does any output. Even a space or newline after the closing ?> tag in the included file would generate output (and thus I normally leave the closing ?> out in my PHP files, just in case).