Same problem, after running without a hitch for several years. I have memcached enabled now but don't think it's used for session storage, so it didn't seem to help.
1883 rows in core_sessions
I will try truncating soon but I don't think it's a great or long-term solution.