Estos headers no podes enviarlos una vez que ya enviaste alguna información, es decir, tienen que ser los primeros datos que envias. Te pregunto, esta página esta incluida en alguna otra? Es decir, ¿llamás a esta pagina desde alguna otra?
Este problema lo solucionas con las funciones ob_start() y con ob_flush(), lee en el manual bien estas funciones asi la podes ubicar bien en tus scritps. Te lo diría, pero no se como lo tenes estructurado...
http://ar2.php.net/manual/es/function.ob-start.php http://ar2.php.net/manual/es/function.ob-flush.php