Cuando todo falla, no olvides consultar el manual
. (
http://www.php.net/manual/es/function.session-start.php). Citando al manual:
Cita:
Iniciado por Manual de PHP Note: Si está usando sesiones basadas en las cookies, debe llamar a session_start() antes de que haya ninguna salida al navegador.
O sea, estás enviando una salida HTML antes de llamar a session_start().