Want to point out that I had the same original problem, replaced the power supply, and it solved everything. The motherboard on that one was replaced only a couple years ago, though, so YMMV.
If you have to install the new power supply upside down, due to the wires not reaching, make sure you strap it in there really good with zip ties or something.