Try these steps with the new key. I'm sorry for the hassle.
Let me know the results.
1. Open command prompt with admin privileges. Always do this when command prompt needs to be run. The best way to do so is to click Start -> Run -> CMD (make sure you run as administrator!)
2. Type in 'slmgr.vbs /upk'.This will uninstall the current key in Windows. Restart your P.C. Run CMD again.
3. Type in 'slmgr.vbs /rearm'. This resets the time needed to activate Windows, and will reset the Windows Genuine Advantage issue, if it’s there. Restart your P.C.
4. Run CMD again. Type in 'slmgr.vbs /ipk <product key here>' where product key represents your product key, including dashes.
• Restart your P.C. when this finishes. Go to Control Panel -> System and Security -> System and scroll and activate Windows. It may take a moment or two, but it should come back as fully activated