You need to replace your motherboard
This definitely sounds like a motherboard issue. With symptoms like your describing my first thought would be PSU, however as you have replaced this with a quality brand I am afraid to say that your MB is a gonna's!
Can I suggest Gigabyte hardware when you buy a replacement. They have the "Ultra Durable" feature, and in my experience these MBs are almost bullet proof.
I have replaced many motherboards in my time - not Gigabyte brand (but instead ECS - don't get me started on ECS!!!) - and I have never seen a CPU fail. Basically CPUs fail about one in a hundred times - the other 99 times are the motherboard!!!