I had the same issue for a while and had a very hard time figuring it out. My problem was that I had the site working for a while with the sessions working right, and then all of the sudden everything broke.
Apparently, your session_save_path(), for me it was /var/lib/php5/, needs to have 777 chmod permissions. I accidentally changed it, breaking sessions completely.
To fix, just do
sudo chmod -R 777 /var/lib/php5/ (or whatever your session_save_path() is) on linux.