Phil,
I understand what your saying. There are a few things to note.. some which may be bugs, others which sound like something else..
When you logout of FB and login with a new user, if you navigate your site, the "mapping" between Facebook and your Joomla account should not be updated at all. This would be a huge security problem if so, so please check in the User Map area of JFBConnect if the joomla user and Facebook user mapping row is correct.
The above is regardless of the avatar that is showing. That could be related, but don't use the displayed avatar as information on what user is mapped.
Another thing that could possibly causing the problem is if you have a mixed domain site. Specifically, if you go to
www.site.com and click around.. does your URL ever update to "site.com" (non-www)? If so, then there would be cookies for the both user's Facebook accounts placed on both domains. While there shouldn't be an update to the mapping, it could explain things a bit more. Mainly, if this is the case, then my guess is that user a is logged into
www.site.com and user b would be logged into site.com (non-www).
Hope what I said makes sense. Mainly, focus on the user-mapping column for now. You really shouldn't ever have to delete users from your system due to JFBConnect's connection of them to their Facebook account.. if so, something is definitely wrong.
Thanks,
Alex