Now that Windows 8 and Windows Server 2012 are out, any company that uses KMS keys needs to add the new ones from Microsoft's Volume Licensing Service Center https://www.microsoft.com/Licensing/servicecenter/Downloads/DownloadsAndKeys.aspx
First, there's a hotfix for your existing KMS server available here:
Once you request the hotfix, get the email and download it, and install. The install will require a reboot, so if you've got this on a critical server you're going to have to schedule a reboot.
A few change request forms and approval signatures later, you'll be finally ready to add your shiny new keys in.
Now, here's the installation instructions from the link above:
If you have a KMS host that is running Windows Server 2008 R2 SP1 or Windows 7 SP1, follow these steps to perform an upgrade: Install this update (KB2691586). Restart the computer when you are prompted. ...