The basic steps are:
1. install the new LS
2. De-activate the old LS
3. Activate your new LS
4. Phone the Clearinghouse and get your licenses re-issued.
5. Install the re-issued licenses
6. Verify that the TS finds the LS
7. If the TS does not find the new LS because you hardcoded the
address of the old LS into the registry, remove the registry entry
306578 - HOW TO: Deactivate or Reactivate a License Server Using
Terminal Services Licensing
http://support.microsoft.com/?kbid=306578
291795 - HOW TO: Locate a Phone Number for the Microsoft
Clearinghouse
http://support.microsoft.com/?kbid=291795