This can be resolve using service account directory path settings.
Use cammand check your existing service account settings :
stsadm -o getsiteuseraccountdirectorypath -url http://mysite/
To remove service account directory path settings use below command. Replace domain with your actual domain name
stsadm -o setsiteuseraccountdirectorypath -path "" -url http://mysite/
After removing these settings you should be able to add new user.
To set service account directory path settings use below command. Replace domain with your actual domain name
stsadm -o setsiteuseraccountdirectorypath -path "ou=domain,dc=domain,dc=com" -url http://mysite/
More info http://mrhodes.net/2009/10/28/the-user-does-not-exist-or-is-not-unique-8/
