To be clear they were deleted and not deactivated, correct? This is one reason I always advise against "deleting" users. If they are deactivated they can easily be reactivated, maintaining historical info.
It is likely that the user still is listed as a user at id.atlassian.com and that is causing the conflict. You can try to have them go to that URL and see if they have an account still there. You may require support from Atlassian Support to clear this.
You must be a registered user to add a comment. If you've already registered, sign in. Otherwise, register and sign in.