This is a common problem, that we have seen many times. It happens often if a
user is deleted from AD without being deleted from Sharepoint and added again,
Sharepoint still keeps a pointer to the old SID.

In many case, this can be resolved by altering the table and location the user
in the Sharepoint Tables and deleting it from there

Can you point me to the
correct tables?

I just figured out where it's located at. You need to go into the SITE
database and open the UserInfo table. Delete all entries that references
that particular user. Once I did that, I was able to add  the user.