у тебя в скрипте не должно ничего выводиться до этого .. ни пробелов, ничего ..
если даже перед <?php есть пробел, то работать не будет

также у меня както возникали проблеммы с хеадерами в юникоде .. так что ставь анси