After setting-up a new CRM server I tried to add new users. Unfortunatelly I got an exception:
Unable to Change Domain Logon Name.

Why??
Users I wanted to add had SystemAdministrator role.

Solution
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.