You've probably checked this, but make sure your Windows operating system is "genuine." There is a diagnostic program which will tell you if it is or isn't. While this might sound stupid, there could be the chance that your installed OS is genuine, but your recovery program could be a mass-processed version that won't install all the things it needs to for your OS to work the way it should.
My OS is working fine - except that it can't download any updates from Microsoft.
Sad to say, Microsoft isn't anyhelp on this either. I think it's just a scam for us to buy more "genuine" crap from them.
Nihil est facile; nihil est gratuitum