What is the computer name you are using? Make absolutely certain that no other computers are using that same computer name. Also know that in NT Server only the first 14 (maybe 12) characters are recognized and if the computer name exceeds the maximum number of characters, you can get errors like that.
Another thing to try is the old take the computer off of the domain (rejoin Workgroup), reboot, change computer name, reboot, rejoin domain and reboot again. That always seemed to work for us.
We experienced this sort of problem when we moved from Win95 to Win2000, but our servers were still NT. Somehow, it seems that the computer name gets "stuck" (for lack of a better word) in NT without appearing anywhere. Taking it off of the domain and rebooting, changing the name, rebooting, etc. always worked.