You are attempting to create a user with a domain logon that is already used by another user. Select another domain logon and try again.
The strange thing I noticed about the error is that, the user I was trying to add was not already there in CRM. I checked this in the SystemUser table and confirmed that it is definitely not there. After tracing SQL Server, I found CRM uses SystemUserAuthentication table to do this check.
Here is the sequence to events
No user A -> Backup organisation database -> User A created -> Restore organisation db from backup
In my situation, the error started happening after I restored the organisation db from the backup. At the time of the backup, the user I was trying to add had not been created. After the organisation db was restored from backup, the SystemUser table in the organisation database does not contain User A, but the MSCRM_CONFIG does (as per SystemUserAuthentication). This is the root cause of this error message.
The fix was to delete the organisation and re-import the organisation from the Deployment Manager. Once this is done, the new user can be added without any issue. This was the additional step I had to perform after I restored the db from the backup.