Are you using the User - Contact Creator plugin? That's the only thing we can imagine. When enabled, it automatically adds a user to the Contacts component. When you delete from the user manager, the Contact remains, and when you try to re-log in, that error will be shown.
If that's not the cause, can you let me know if that's the exact error message you receive? Also, can you check that in the Joomla User Manager and JFBConnect Usermap area the user is actually gone? Not sure what could be causing it otherwise.
Thanks,
Alex
Error after deleting contact
