Ante un session_start() .. y luego un header() no debe de darte problemas de encabezados ..
Donde da problemas de ese tipo es cuando antes de ese header() tienes HTML, o echo "algo" .. q envies al navegador .. Incluso un espacio o salto de linea <? antes del incio del script es considerado como "envio de cabeceras" .. Revisa si tienes includes() q llames .. usa lo mismo .. q empiecen <? sin espacios ni saltos de linea delante.
Si tienes mucho HTML por medio y pocas ganas de ir moviendo el código .. puedes usar funciones para gestionar el buffer de salida ..
http://www.php.net/manual/en/ref.outcontrol.php
seria mas o menos:
Código PHP:
<?
ob_start();
//Tu codigo actual ..
ob_end_flush();
?>
Un saludo,