I had a client's computer do the exact same thing. We replaced the power supply, reseated the processor, and nothing helped.
Since all computers require 3 things for bootup: video, RAM, and a processor, I decided to systematically troubleshoot the basic items.
It wasn't the video, since it didn't instantly freeze the computer. It wasn't the processor because the temperature was fine, and I had already reseated it. It wound up being the RAM -- the RAM was going bad.
Find a free RAM testing utility on the Internet. Since my client had a Compaq computer, we used the "Compaq Intelligent Manageability" program. We used the Diagnostics, and tested 'memory'.
If replacing the power supply doesn't help you, you should try replacing the RAM.