Uninstall terminal services and licensing in old server, install terminal services on new server, enter license and activate - you may have to call MS activation in worst case.
Or you can install terminal services in new server and point it to old servers licensing server - they both will share same license (in case you will leave old server in operation)