Copy of Windows is not Genuine

For the past several days I've seen a notice pop-up on my Windows 7 computer saying that my copy of Windows is not genuine, and another saying I may be a victim of software counterfeiting.  I've been using this computer for at least 6 years and it was definitely a legitimate purchase.  

What did happen is that at the beginning of March the motherboard fried on this computer. I replaced the motherboard and image-restored the hard-drive (Acronis). Everything worked fine, but now I'm getting this message. Certainly the change in motherboards triggered it.

Now, what to do? The notice box gives me a link to "Go online and resolve now", which gives me the option to "contact support". The contact support link gives me a tool to run: "Microsoft Genuine Advantage diagnostic tool", which I have run and copied the results. Instructions (http://windows.microsoft.com/en-us/windows/help/genuine/submit-request):

How to submit a technical support request

1. Open the Microsoft Genuine Advantage diagnostic tool. Click Run, and then click Continue. 

The tool will scan your computer, and then give you a summary of your computer's settings and system details that will help the support team understand the problem.

To copy your results to the Clipboard, click Copy. 

2. Visit the Microsoft Support page to see what type of technical support is available in your area. 

3. If you choose e‑mail support, follow the prompts to submit your support request. Note that you may be prompted to download an ActiveX control. This is not required and you can continue without installing this control. 

• Enter your contact information. 

• Enter the following information in the Problem Description text box: 

• Paste the information copied from the diagnostic tool in Step 1 above. To do this, right-click in the text box, and then click Paste. 

• If you have additional details or comments for the support team, type them at the end of the same text box. 

• If possible, also include the product key found on your Windows Certificate of Authenticity (COA). The product key can often assist our support engineers in quickly determining the cause of your validation issue. To see examples of COA labels, go to the Microsoft How to Tell website. 

• Fill in any additional information requested on the page and click Submit. Your request will be sent to the Windows Activation technical support team. You will receive a confirmation number via e‑mail that you can save for future reference. 

Select allOpen in new window

My problem here is that when I go to the "Microsoft Support" page, I get no "e-mail" support" option. I am lead to a page where I can sign up for paid-support. Of course, I'm not about to pay for support for a product I already own -- it would be cheaper to install a new version of Windows 7.

Any suggestions on what to do?