Okay, thanks.
1. How are your temperatures since reapplying the thermal paste?
2. Update the BIOS if available.
3. Before and after updating the BIOS, clear the CMOS. Don't overclock, adjust any settings, etc.
4. If the above fails, you have a faulty CPU/motherboard given the provided information. I cannot tell you which one, but if there's warranty/replacement available for both, I would replace both.
Regards,
Patrick