Well, certainly check for viruses and spyware, even though it is brand new. Some legitimate software will also install spyware, so it is worth a look. I use Spybot Search and Destroy, an excellent freeware tool.
But I, like you, suspect bad power. If the voltage coming off the power supply is adequate and non-fluctuating, try a line conditioner, or use a different UPS or even a different outlet to power it. At work we had a similar problem and traced it to a piece of equipment in our shop. Every time the shop worker used the machine, the computer rebooted. Turns out the PC was plugged into the same circuit as the machine, and when the PC got the spike it died. Since it just started happening, we theorized that the power supply in the PC had degraded to the point that it could no longer take the spike. You've got a new supply, but you may still have dirty power.
Also, try removing any cards not strictly needed, like network or scanner interfaces. I had a bad network card fritz a machine once.
May also try resetting the BIOS to defautls. Or removing some of the RAM if it is in several DIMMs (try swapping the DIMMs out, using just one at a time).
That's all I can think of. I hope you get it going...