Windows 7 is not genuine after rolling back from Windows 10

A little background story:
I upgraded to Windows 10 while it was free, then rolled back to windows 7 within 30 days for the sole purpose of getting a “digital entitlement”. I didn’t use my PC for months, but today I thought of turning it on and see how my pc is doing.

Problem:
Once at the desktop, a dialog box pops up saying "You may be a victim of software counterfeiting", and saw that my windows is not genuine and I need to apply a product key. I used ProduKey to get the product key of windows 7 I had before the upgrade, but using it gave me error 0xc004e003. I tried to apply the key again, same error. I looked up on microsoft (link:https://support.microsoft.com/en-us/kb/931276) and tried their solution (Method C) which prompted me to Method G, to use the automated telephone system, which doesn’t appear as an option in my PC.
Any suggestion on how to solve this problem? And how did the Windows10 recovery process loose the Windows7 product key?

Thank you in advance

Once you upgrade to 10 it appears that the key is converted to a 10 key with downgrade rights to Windows 7. So likely your key that came with the PC has changed in the installation. Calling Microsoft may help, but they may redirect you to your manufacturer for assistance. Having the key on the sticker with the machine is your best bet. Re-run activation and use the phone activation instead.