Hola chechu_
el header no funciona si ese script ya ha mostrado algo por pantalla (es decir, ya se ha enviado el header al navegador).
Para solucionarlo, lo que yo suelo hacer es, al terminar la ejecución del script php, añadir el javascript para la redirección:
Código HTML:
/* Fin del código php */ ?>
<script type="text/javascript">
document.location = "pagina.php";
</script> No se si hay una solución más adecuada, pero esta funciona.