Are you using DHCP or not? If so, you can rename this computer without any problem. On the computer, you should be able to rename it by right clicking My Computer then go to Properties > Network Identification > Properties. However, this won't work if the machine is a Domain Controller. If that's the case, you have to demote it by running the DCPromo command again. Then you can change the name and promote it.
I'm not sure if you'd have to change the name in the DHCP Server or not. You might want to double check that.
However, if your network is using static IP addresses, you won't be able to do this seamlessly. You'll have to go to each and every computer and change the name. If all the client computers are shared, you could probably do it from your own workstation. If not, expect to get some exercise. @=)
Hope this helps.
Catadmin - New to Server Admin, but willing to learn... All help is appreciated.