After setting-up a new CRM server I tried to add new users. Unfortunatelly I got an exception:
Unable to Change Domain Logon Name.
Users I wanted to add had SystemAdministrator role.
Edit registry entry at HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\MSCRM and change AutoGroupManagementOff to 1. After that reset IIS and try to add user again.