Ran into this issue today while trying to create a new user in CRM 4: “The specified Active Directory user already exists as a CRM user. 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.”
After investigating, I ran across this extremely helpful article from MSDN UK. It walks you through tracking down which CRM user corresponds to a particular Active Directory user (SID), which unfortunately has to be traced through three separate SQL tables. Turns out my AD user had been assigned to another user’s CRM account for some reason, and the CRM account disabled.