Sounds like power supply to me, too. Take it back. They probably put some crappy psu in it. Do you have a GPU? What's the make and model of the PSU? What's the amps on the 12volt rail? There should be a sticker on the PSU that states how many amps.
oh, put the temps in Celsius, not that other format, please.