Like I said - there should not be any output before header line.
Even empty line that is not in the php script body (not between the tags) is an output. An example:
<?php
$foo="www.yahoo.com";
?>
<?
header("location: $foo");
?>
will not work, because there is an empty line between two pieces of code.