Un error clasico y muy tratado... Cuando trabajas de modo local, me imagino que es en windows, con un apache, etc etc... Esto es muy permisivo, cuando lo subis a linux, la realidad es otra, y es cruel, pero segura...
Si no me equivoco el tema es que ya abriste y cerraste un <? ?> cuando iniciaste session, ahi se enviaron los headers... Esta es una gran cagada de PHP, deberia tener algo simple y no problematico como el response.redirect de ASP que nunca jode y siempre anda...
Lo que suelo hacer es un echo, de un javascript para redireccionar, en lugar de los header location... Te pongo una muestra...
Código PHP:
echo "<script>document.location.href='pagina.php'</script>";
Suerte!