I discovered this error message on several servers in a new Windows 2008 domain. This issue occurs because you have more than one KMS hosts in your organization, which is the usual case.
Just like written in this thread on the Microsoft TechNet Windows Server Forum, there are several ways to solve this issue. In this case I used the simplest one; create the SRV record manually in the DNS.
1. Log on to your DNS server and open the DNS manager.
2. Navigate to the Forward Lookup Zone/<your domain>/_TCP.
3. Right click on the right window and select Other New Records… from the list.
4. Scroll down and select the Service Location (SRV) record type and click Create Record.
5. Fill in the fields as follow:
Service: _VLMCS
Protocol: _TCP
Priority: 0
Weight: 0
Port number: 1688
Hostname: <FQDN of the host that logs the error>
6. Click OK to create the record and click Doneto close the Record Type window.
7. Go to the host that logs the error and restart the Software Licensing service.
After the Software Licensing service has been restarted you should see a Security-Licensing-SLC 12294 message in your Event Viewer stating that the publishing of the Key Management Service to your domain was successful.
Cheers!
– Marek.Z