A while back, I'd set up a Server 2008 R2 Standard Domain Controller (physical box) to act as a KMS server for a few dozen Server 08 R2 Standards running on Virtual Machines. Things seemed to work well, but I started getting tickets for newly cloned servers needing activation and I know something had gone wrong. I re-keyed the KMS server and made sure that it was ready to accept requests. I got 6 or so Client VMs setup with it as the KMS server and with MS's preferred key for Windows Server 2008 R2 Standard : YC6KT-GKW9T-YTKYR-T4X34-R7VHC. I had each of them request activation with slmgr.vbs /ato, (which failed) The highest I could ever get was 3 on the current count, which didn't hit the threshold of 5 before it starts working. 

---------------------------
Windows Script Host
---------------------------
Software licensing service version: 6.1.7601.17514
Name: Windows Server(R), ServerStandard edition
Description: Windows Operating System - Windows Server(R), VOLUME_KMS_R2_C channel

Activation ID: 8fe15d04-fc66-40e6-bf34-942481e06fd8
Application ID: 55c92734-d682-4d71-983e-d6ec3f16059f
Extended PID: 55041-00168-305-984134-03-1033-7601.0000-2472015
Installation ID: 012314785241011660170610893610784203126865493373820695

Processor Certificate URL: http://go.microsoft.com/fwlink/?LinkID=88342
Machine Certificate URL: http://go.microsoft.com/fwlink/?LinkID=88343
Use License URL: http://go.microsoft.com/fwlink/?LinkID=88345

Product Key Certificate URL: http://go.microsoft.com/fwlink/?LinkID=88344
Partial Product Key: X2PTJ
License Status: Licensed
Remaining Windows rearm count: 2

Trusted time: 9/4/2015 6:34:42 PM
Key Management Service is enabled on this machine
    Current count: 3
    Listening on Port: 1688
    DNS publishing enabled
    KMS priority: Normal

Key Management Service cumulative requests received from clients
    Total requests received: 11
    Failed requests received: 3
    Requests with License Status Unlicensed: 0
    Requests with License Status Licensed: 0
    Requests with License Status Initial grace period: 0
    Requests with License Status License expired or Hardware out of tolerance: 0
    Requests with License Status Non-genuine grace period: 0
    Requests with License Status Notification: 8
---------------------------

Besides not activating, now several of the clients have the black desktop backround and 'This Copy of Windows is not Geniune". After reading up on this, the advice was to get a different key as it was thinking the default one is wrong or fake and thus useless.  I've Googled and read and can't find any other keys to use than the one above. Any ideas?  Thanks!

Here is a link that should help with troubleshooting and fixing the issue you are experience

click here for kms troubleshooting

Be sure in your DNS, in the tcp_ip section that the correct server for kms (VLSC) is listed.

Sometime if you add by error a second server as a kms server, it will add another entry there. Thus the client are not directed at the good place.