I have mentioned this many times before but renaming accounts via WHM is broken and does not update everything that needs to be updated and leaves a lot of underlying things broken until you do some manual updating in the system to fix those issues.
Bottom line though is that it is really not a good idea to rename the domains on accounts using WHM.
Now with regard to where you are running into a conflict ---
Code:
# grep "domain.com" -- /var/cpanel/users/*
That will tell you which account login has the old domain and if not actually active, you should be able to remove the "DNS" or "XDNS" lines from the account file and update the users database.
Also you mentioned "servers". If indeed you are actually running multiple server machines and not talking about just separate hosting accounts, you will also run into problems if those server machines are under the same DNS clustering as this will also prevent you from adding any domain that already exists elsewhere within the clustered servers.