As with the grief of auditing licences et all, you may sometimes find that you need to do a site-wide change of the licence key for Windows Server or Windows XP.
Microsoft have helpfully provided two scripts that will allow you to change the product licence key programatically.
Just run the script with your new VLK, and everything should work wonderfully.