btys:
First, please verify if your COA sticker or product key (http://www.microsoft.com/resources/howtotell/en/coa.mspx) matches your Product Key being used on your system? You can view your product key with the Genuine Advantage diagnostics tool (at least the last 15 digits) located here: http://go.microsoft.com/fwlink/?linkid=52012 .
The Genuine Advantage Product Key Update Tool is only valid for users attempting to change their current non-genuine Product Key to a genuine COA sticker or genuine Product Key – all without a reinstall! http://go.microsoft.com/fwlink/?LinkId=50346&clcid=0x409
Good luck!
Greg