In my experience this has been caused by either a short (a loose screw on the motherboard somewhere) or a bad power supply.
You can pull the power supply, short the green and a black wire (this turns it on and must be done) and test (with a volt-meter) that all the 5V connections are providing about 5V, the 12V connections about 12v, the 3.3V about 3.3V, etc. And you can test each ground as well.
Also, applying thermal compound on the CPU is something you should get comfortable with. I think it is a good idea to every year or so completely tear down the computer, clean out all dust, remove the CPU heat sink, clean off the thermal compound, and apply fresh compound.
Yes it CAN be a power supply problem. My last power supply was going bad and it could run for days some times before the computer would "randomly" shut down. Other times, it would only be a few seconds after turning it on and it would shut down.
Yes the CPU CAN over-heat after only a few seconds. Its a built in safety device. CPUs heat up very quickly when their cooling system is not working properly.
-Chris P