The 8059 error typically means that the key has been used before. If you received this the very first time you activated, or attempted to, I suspect that your key is a duplicate key. You can contact support to have them verify this or simply exchange the retail package at the retail store, if possible, explaining that you want an exchange as the key has been reported as used.
How to reach support - http://forums.microsoft.com/WindowsOneCare/ShowPost.aspx?PostID=2421771&SiteID=2
Since you cannot validate a subscription, select the option that you are using a trial or beta copy and you can proceed to email support without validation once you've signed in.
-steve