Creo que desde hace muchos mensajes encontramos la causa: Más de un session_start(); se ejecuta en tus scripts, pero tú dices que están bien puestos.
Sugerencia:
Supongo que tienes un archivo que incluyes en todos tus scripts, ya sea de conexión a base de datos, configuración, funciones comunes, etc.
Coloca ahí la línea session_start(); y elimínala en todos los demás archivos, asegurándote de que no hay una salida previa (caracter, espacio en blanco, salto de línea, etc.).