Actually, upon further tests, sessions are working correctly for regular users. They are not however working for Facebook Connect users.

Please clarify, are you saying when a Facebook user hits your website they are logged in but they have no corresponding row in the sessions table? That doesn't seem possible.
Or, are they not logging in at all?

Yes, when a Facebook Connect user is logged in, there is no session row for them in the database. They do have a session cookie though. I tested it with my Lovinity account since it's facebook connected. I browsed around several pages and never got a session row in the database despite being logged in.

What I find weird is that this was working just fine on Thursday. Then sometime between Thursday and Saturday it's not working anymore. I didn't change anything on site.

Didn't reproduce, but we'll assume it was because sessions weren't written if the table is locked. Maybe there was heavy load on that table for some reason, or racing between multiple parallel requests, or MySQL wasn't good at keeping track of locks.

I'll remove the table lock check from that table.