Your question is somewhat lacking in detail, so I'm going to have to make the following assumptions.
- You are using Active Directory, and the server is a member of the domain.
- DNS is running on your domain controllers, and accepts dynamic updates.
If these assumptions are incorrect, please edit your question and add the correct details so a better answer can be provided.
When you rename a computer that is a member of an Active Directory domain, the computer will attempt to re-register itself in DNS, and remove the old DNS entry.
You don't specify how you are querying DNS? Are you using nslookup or similar, if so, you might be seeing cached results.
nslookup MyServer actually resolve? If so, you might find that
ipconfig /flushdns (or a little patience) is all that you need to clear the old name from your DNS queries.
If you aren't a member of an AD domain, or you aren't using dynamic DNS, then the chances are that you will need to manually update your DNS records, or switch configure your DNS server to accept dynamic updates. A little more info in your question will help you get a better answer if this is the case.
Edited answer for updated question:
You have two options, either enabling dynamic updates on your DNS server, or probably easier in your configuration, just update the DNS records manually.
To configure dynamic updates in the DNS server.
1. Configure your server
On your server, open the DNS administrative tool and expand the tree to show your server, and expand
Forward Lookup Zones. Right click the relevant forward lookup zone and click properties, on the general tab, you will find the
Allow dynamic updates dropdown box, you need to select the option that allows 'non secure updates' for your configuration. Click OK to close all dialog boxes.
2. Configure your clients
On each workstation, open the properties for the network interface, and drill down into the TCP/IP properties. You will find a DNS tab, which contains two checkboxes at the bottom for 'Register this connection's address in DNS' and 'Use this connections DNS suffix in DNS registration'. Ensure both of these checkboxes are ticked.
Update the DNS records manually.
In the DNS management tool, locate the out of date DNS A Record for your server, right click on it and select 'Delete'. Now right click on a blank part of the screen (or right click on the forward lookup zone) and select the option to add a new A record. Give the A record the new hostname and the IP address of your server.
If you're planning to add more computers to the network in the future, you might want to consider adding active directory to your network, as it makes configuration of systems so much easier. Be warned though, you really should have a minimum of two domain controllers, and don't make a server into a domain controller if it is exposed to the internet (e.g. runs a public IIS or mail server).