Ten en cuenta que para usar la función header() NO PUEDES haber enviado ABSOLUTAMENTE NADA al cliente.
Es decir, sólo funcionará si es lo primero que pones en la página que mandas al navegador.
ERROR:
Código PHP:
<html><?php header(); ?>
OK:
Código PHP:
<?php header(); ?><html>