I wondered if there was something left behind in the database that caused the issue, but I didn't know what to look for about that.
When you delete a user through Joomla it does not delete them from CB. CB Connect checks if a CB user has the social site id associated with them already then behaves accordingly. If however you deleted them from Joomla and not CB then they only half exist. So when it finds a user that is already associated with the social site id it trys to login, but it can't because your Joomla user is gone and you have no username.
So it sounds like I should be deleting users through CB instead of Joomla, and if I run into the same problem I'll figure out how to run a synchronization.
Correct, when CB is installed you should always manage your users from CB > User Management.