Earlier quoted context omitted.
"No, a windows user would have to buy a second copy of windows from microsoft" Or procure a legit, OEM install disk/image and reload using the key affixed to the bottom* of the laptop. *Pre-8 days, now you get to "hope" the gUEFI recognizes the media and auto-populates the embedded key for you. When(not 'if' in my experience) it doesn't, then "buy more" is the only option outside of Linux.
This is totally correct - I just meant that using Lenovos provided installation media would not resolve the issue. You can definitely use an OEM disk of your exact version with your printed serial. I too have had to procure new keys for win8 machines (did two last week that wouldn't recognize the keys on my machine)
What you may of had issue with was your OEM license being activated too many times -- if that happens, the automatic online activation will not work. You must use the phone number to activate your license, and it will ask "how many computers is this license installed on"... of course you just give the answer "one" and it activates it with no problem.