Remote Site in AD cannot see new 2003 License Server, in the Licensing forum on BrianMadden.com

We have been running License Server on an old W2000 server and a newer W2003 server. We recently implemented VMware ESX and I want to get rid of the 2 old License servers and build a new one with the VM structure.
Initially, after I installed License Server Licensing, my Terminal Servers on the local site could not see the new License Server. Specifying the server name in TS Config seemed to sort this.

My problem is with our 2nd site (within the same AD). It cannot see the License Server (it can ping it etc). If I try to do a license server discovery, I get a "Cannot validate License Servers" window popping up.

I have noticed that in the License Server discovery window, it displays "Automatically discovered license server" - "In the Enterprise Role" - and shows the OLD license server.
Currently I have just stopped the licensing service on the 2 old servers - do I actually have to Uninstall Licensing manager from them or should stopping them be enough.?

There are no errors in the event viewer on the remote terminal server.
The installation of TS licensing on the new server seemed to go without a problem.
This AD was originally a Windows 2000 one with newer 2003 Terminal servers added.
We are running both 2000 and 2003 Terminal Server.
The remote site is connected by a 512kbps WAN link.
The new license server seems to be issuing CALs to clients in the main site.

Any suggestions on getting my remote site to see the new License Server ?
Thanks in advance.
Steve

Just disabled the Windows firewall on my new VM W2003 server and my remote server can now see the License Server. Does anyone know which ports I open for License server discovery?
My Terminal Servers are still seeing the old servers in the "automatically discovered license servers" section though, which can't be right as they are turned off ?