So pretty as the question states, here is some more info:
What I have done:
1) I have setup 36 machines (I have more, but just done one lab for now) to point to the KMS Host
2) I have rearmed the host and again setup the 36 machines
3) The KMS Host is a 2012R2 machines
4) The clients are all Windows 7 enterprise and there are 3 2012R2 and 1 2008R2 server part of this pool
5) I have disabled and re-enabled the firewall
6) I have checked and confirmed my dns settings
7) I can ping the KMS host machine from the clients
The images below show that I have the numbers, but I am still getting the insufficient count message.
From the KMS Host:
From a client Machine:
The host key I have installed is for 2012R2-Windows 10