What is best practice for changing a user name on a domain?

Heavens no don't make a new account. In Active directory, you can just change the name of the account to match the new name. On the exchange server go to the active directory users and computers snap-in and change the smtp properties under the address tab. You will want to add a new smtp address for that user reflecting the new name and set that one as the reply address. Keep the old smtp address as well for now that way the old addy will still be valid. Change the display name in the General tab in active directory. You can also change log in name to match the users new name but make sure you tell them first so they don't have trouble logging in.