Active Directory Rename

I have the following situation. Upgraded to a 2003 domain controller fron NT4. In the process, the domain was set as "xxxx.zzz" instead of "xxxx".

My issue is that when a user's password expires, they cannot find the domain to change their password. This is happening on all clients, be it, NT4, 2000 or XP.

If I rejoin the domain with the affected PC, then it finds it just fine and the user is able to change password, etc.

I was thinking of renaming the 2003 domain to "xxxx" but I wanted to avoid this if I could.

Has anyone in here used the AD rename tool? Any tips? Any easier way to do this? Suggestions?

Update:

As suspected, I cannot duplicate these problems in my lab at home. Followed same setup, etc.

Which leads me to believe I have a WINS or LMHOSTS file problem.

Can anyone suggest a good way to update LMHOSTS across a domain (preferably delete the d@mn things)...