Before anything else - try another browser!
I just encountered this session_start problem. I checked my tmp folder and everything and I was about to call my hosting-provider until I thought I should try another browser first because it might have to do with session cookies.
I work with chrome, so I tested in IE and found that it was indeed the case: It worked in another browser!
I closed IE ;) - went back to chrome, looked for the cookie (PHP_SESS_ID), deleted it and everything works again!
Well, the good part is - Just like you guys I got to brush up my knowledge of -jay- sessions! ;)