Active Directory user names: why does the canonical name vary? Can I do something to make them uniform?

Active Directory does not really concern itself with how the User account object's RDN (the last part of the Canonical Name) relates to other properties like the Display Name or the Logon Name - as long as the value of each individual attribute doesn't violate the schema definition.

The behavior of the "New User" form in Active Directory Users and Computers (as well as a number of other dialogues) has changed significantly between Windows Server 2003 and Windows Server 2008 R2 - and that's probably why they're not consistent

You can use PowerShell to move the non-system accounts, and then go through the users and rename them to whatever their Display Name is:

# Create new OU named RegularUsers
New-ADOrganizationalUnit -Name RegularUsers -Path "dc=domain,dc=com"

# Retrieve all users that are not critical system objects
$users = Get-ADUser -SearchBase "CN=Users,DC=domain,DC=com" -SearchScope OneLevel -Filter {-not(isCriticalSystemObject -like '*')}

# Go through each and move to the new OU
foreach($user in $users){
    Move-ADObject $user -TargetPath "OU=RegularUsers,DC=domain,DC=com"
}

# Retrieve all users in the new OU
$movedUsers = Get-ADUser -SearchBase "CN=Users,DC=domain,DC=com" -SearchScope OneLevel -Filter '*'

foreach($user in $movedUsers){
    # Test if Display Name and object Name is the same, if not - rename
    if($user.DisplayName -ne $user.Name)
    { 
        Rename-ADObject $user -NewName "$($user.DisplayName)" 
    }
}

For the first step, you could also just highlight all the user accounts in ADUC and drag-n-drop them to another location.

The CN/DN of an object is not all that relevant, as it is only used internally by AD and in LDAP queries; end users (and administrators) very rarely get to even see it. It actually changes on its own when you move objects around, because it includes the full LDAP path of the object.

If you want to standardize it, this can be done without any side effects; the only thing users are actually concerned with is their logon name, and as long as you don't change that, they will continue to log on as usual.

To change it, you can either use the ADUC console, or the PowerShell command Rename-ADObject.

The dsmove command should be able to change the canonical name for you. I've done this in test environments but never in live environments so I would advise proceeding with caution.

Also, semi-related, I would advise implementing another domain controller to avoid a headache should your only DC go down.