Since cleaning the heatsink helped, I would next want to be sure the CPU is pasted well and not frying. You can physically inspect it or enter BIOS setup at boot to watch temps.
What are the current BIOS settings to shut down at high temps? What temp is read?
What happens when you remove the components one-by-one as suggested earlier: HD, DVD drive, Video card, keyboard, mouse?
I am repeating myself here because you are unresponsive to these steps given twice earlier. In order to troubleshoot hardware now we need you to be fully interactive and responsive to every step given.
If a component isn't causing the shutdown, and all connections on the mobo are good and not shorting, then I would try another PSU to see the difference after recalculating the Power needs. You can call ahead and go into the Geek Squad when they are not busy and they will plug in a power supply for you to test this.