Tal vez estés ejecutando ese PHP dentro de un HTML que ya contiene encima de ese código un header.
No debe de haber código HTML encima de la invocación a header()
Y si te da muchos dolores de cabeza, prueba a redireccionar con javascript
:
Código PHP:
echo '
<script type="text/javascript">
document.location.href="pagina";
</script>
';
Saludos.