Si tienes algún include() .. que llamas a código -antes- del session_Start() .. también asegurate de que este no tenga ni un espacio, salto de línea al final del mismo ?>
Cuando usas sesiones (cabeceras HTTP en general ..) no puedes hacer cosas como esta:
NO correcto Código PHP:
<html>
<head>
</head>
<body>
<?
session_start();
// etc ...
?>
</body>
</html>
Correcto Código PHP:
<?
session_start();
// etc ...
?>
<html>
<head>
</head>
<body>
blabla
</body>
</html>
Un saludo,