From the description it looks like faulty thermal control of the motherboard. Also, it's not clear for me: did you applied just enough thermal paste or were generous with it?
Solutions I see right now are:
- Update BIOS of your new MB. Quite often that does the trick on both cpu running too hot and fan not working correctly.
- If you used a lot of thermal paste it's not good. Paste is not good thermal conductor, you should use as little as possible. In essence, it should fill micro-cracks and other imperfections ion the contact surfaces of both cpu and heatsink. If you did that already (use minimum amount of paste that is), no issue.
- Fan may have developed a fault. If #1 option is unsuccessful, check with other fan that is known to be working properly (just for tests, so it may be old one). But the cpu is mite too hot, so it may be it's just compensating for that.
- Are you sure you connected the fan to the cpu_fan connector? I know... But better to make sure. You have quite a lot of connectors there.
- Make sure you placed and locked the heatsink correctly.
I know most of what I wrote is really basic stuff, but please believe me, I made all of the errors above at one time or the other. If all that fails, it may be that new MB is faulty... I've seen that happen as well.
Windows not genuine is normal after MB replacement - you need to contact Microsoft on that. They will sort it out.
EDIT: afterthought - did you set up BIOS settings of new MB to default? Maybe it's overclocking the CPU on current settings?