Fíjate que no haya NINGÚN tipo de salida antes de invocar a session_start() o header(). O sea, ni siquiera un espacio en blanco debe haber. Por otro lado, si ya quitaste toda salida y aún no funciona, revisa esto:
http://www.forosdelweb.com/2023067-post176.html