First off, it's important to understand how the clients locate their server; I've documented the process many times before, and just recently I've gone through some of the changes to GSS 2.5 that relate to this, but the basics are the most important bit.
When the management server is first installed on a machine that has never had GSS on it before, it creates a simple self-signed digital certificate for itself, and the private part of the certificate is stored in the PRIVKEY.CRT file in the installation directory while the public part is stored in a file named PUBKEY.CRT
As part of locating a GSS server, the clients do several things; their idea of which specific server is managing them comes from that certificate, and as part of communicating with the server they require the server to mathematically prove that it has the private key to match the public key they have. This, combined with the fact that it is the clients that contact the server, means that the clients are assured that they only receive commands from the specific legitimate server which is allowed to manage them.
[ Some third-party management frameworks do not do this, and allow malicious users to easily remotely control and install software on the machines under management given any direct access to the network on which the machine resides. ]
When a GSS server is uninstalled, it copies its old database and the PRIVKEY.CRT/PUBKEY.CRT files to a location (I believe under C:\Documents and Settings\All Users\Application Data\Symantec\Ghost for Windows prior to Vista and whatever the equivalent is for Vista and Win7) so that if it is later reinstalled on the same machine, the server will reacquire its original identity and the clients will be able to locate it. Indeed, this process is part of the normal MSI upgrade procedure when moving between GSS versions.
Note that the GSS server backup utility included in the product and also available from http://code.google.com/p/gss-scripts/ takes particular care to capture these security certificates, which is how that backup utility can also be used to transfer GSS server installations between machines.
From your description, it sounds as though somehow your new GSS server installation has not retained the private certificate from the original installation. If so, then you should consider trying to recover the certificate file from a backup of your original installation. Otherwise, you can consider trying to distribute the PUBKEY.CRT from the new server installation to the existing clients by some means and seeing whether that helps, as it should.