You DO NOT need to create a new keypair (despite some clueless Technical Support people claiming otherwise, despite my numerous explanations to the contrary over the years). Since Connect's search is so broken, it's probably time to reiterate how all this works once again.
The first thing is that the keypair not only establishes the security of the connection between client and server (as the clients perform a challenge-response verification of the server's private key as part of discovery) but as well the hash of the public key is also the primary name of the server. In any properly configured network, both the server discovery and the challenge-response verification are done with a single multicast packet, and **at no point does a server's name matter at all**. This mechanism was designed by me for the first release of the management system in 1999 and remains the primary one.
Much later, I added a fallback system for people with incorrectly configured networks that did not support IP multicast. Since customers without working multicast often didn't have any alternative service that we could rely on either, the fallback protocol with the highest probability of working at the time was NetBIOS, and so additional data was added to the server and client certificates to embed the server's NetBIOS name and to allow matching up that way (this design was also picked up by Ghost and the GhostCast server to perform matchmaking for manual sessions on non-multicast-capable networks).
[ Note that this fallback is used only to get a potential IP for the server; the challenge-response iteraction to prove the server's identity still takes place, it's just done in separate exchange over unicast instead. ]
The problem with using names for this - and why I consciously chose the primary design to not need them - was the problem of server moves. This problem is even harder when you realise that thanks to Ghost winding back client machines in time, when a server is moved then the old name is embedded in every single client image. To cope with this, when the server machine's name changed I made the server still recall its original machine names and the server continues to register itself under the NetBIOS name used when it was first created, thus allowing older clients to continue to be able to contact it.
At some point - probably around GSS 2.0, from memory - I made the DNS name of the server (as embedded in the PUBKEY.CRT file along with the NetBIOS name) visible to end users in the notification applet. Unfortunately, by making the embedded names visible, a lot of GSS users took this as a basis to assume that the names were what the system actually used behind the scenes, leading to some confusion (including the aforementioned incorrect advice promulgated by Technical Support) about how server moves work.
So the next iteration of this was to ensure that, as part of the normal client upgrade processing done whenever a task is run against a client, the clients were explicitly sent a new PUBKEY.KEY file from the server if it had changed. So what should be happening in GSS 2.5 is that when the server detects its machine has been renamed it will generate an updated PUBKEY.CRT, and then as tasks are run against clients that updated certificate will be sent out - the new certificate won't take effect immediately but it will be read the next time the management client starts.
This means that over time (exactly how long depending on the frequency with which tasks are run, machines reboot and how long the machine images with old certificates stay in active use) the clients should converge on displaying the new server name. This also helps with a corner case in the old scheme, of how many old NetBIOS names to retain on the server to cope with multiple renames.