Maybe, just maybe having 500 stored sessions, it randomly started recycling some of the session ids's. The idea of it doing that would be mind boggling when you consider the hash is 128-bits, but considering;
1) the sessions table hasn't been cleaned in forever
2) we get thousands of hits a day
It's possible. Unlikely, but possible.
Hopefully, deleting your cookies and caches, then logging in again will help because honestly I'm not sure what else to do at this point.
Wayne