APC could actually be the problem. Depending on how it's configured, it may be caching some of the code of JFBConnect in a way that user (a) logs into your site.. the login flow is cached with that user. Then, when user (b) logs in, the flow from (a) is used.
APC generally works well, but there are issues like that that can happen. We use eAccelerator on this site. Not saying it's better, but we tested for weeks under a ton of different scenarios to make sure the caching didn't mix information.
Beyond that, I'd recommend trying to disable the Invitex and JComments user plugins for now. I can't imagine they are the problem, but during login, each User Plugin is fired off and can change the session information. If one of those has a bug, that could be the problem.
If the user's aren't in the JFBConnect User Map table, I can't imagine any scenario in which JFBConnect would connect them to the wrong account. You don't have multiple databases running or backup tables somehow remaining in your database, do you?
Finally, you may be right that the problem is with the sessions table. However, the sessions table is 100% managed by Joomla. If your site is having issues with the session table where data is getting used by the wrong user, that's either a server configuration (APC, etc) or a major bug in Joomla. Just to clarify though, when you restart apache, if you clear the session table, the issue completely goes away? The sessions are related to a cookie stored on a user's computer. Even restarting apache shouldn't alter the cookie or corresponding value in the session table, so I'm not sure how restarting apache would affect that.. but it's a good data point, if I understand right.
Thanks,
Alex