First thing is how are you handling sessions, are you using a cache like memcache?
Second, have you tried emptying the sessions table, maybe it's become corrupted?
Third, this is probably a long shot, but have you tried running the tools in the cb admin panel to sync users and check the database tables?