Debes usar session_start() antes de cualquier otra cosa, antes de usar incluso header() ¿lo estás haciendo así?
Y por favor, muestra el código completo, así únicamente oscureces la información asumiendo cosas que crees están bien, pero eso es lo que tu ves.
Es necesario ver lo que haces en realidad, porque es obvio que si sigues teniendo un error entonces algo estás omitiendo.