Seguro que no haces ningun echo antes de el header...
Prueba lo siguiente, pon al principio del todo de tu pagina
Código PHP:
<?
ob_start();
?>
Y al final (No es obligatorio pero sino lo digo cluster se enfada :))
Código PHP:
<?
ob_end_flush();
?>
Si entonces te sigue fallando es que tu hosting te inserta algo de codigo al principio de tu web.