You may have already tried this but, and forgive me if I state the obvious
First, disconnect ALL devices not essential to basic operation
ie. unplug your speakers, printers, usb devices. Then open the case up and remove *ANY* expansion cards you might have installed (modems, soundcards). The disconnect the drives from the system
By this point you should have a motherboard with a graphics card, memory and CPU. Nothing else.
Now, double check the CPU heatsink/fan, and all power connections
Leave the case open, and power her up. Does it behave now? OK, you can't test windows like this, but basic operations at what you're looking at. While the case is open, check the CPU fan is spinning. If problems persist , hop into the BIOS setup, and find the option to reset to default (a "failsafe" or "conservative" option if you have a choice of several defaults)
Check the CPU settings match the actual CPU!
If after this, it still misbehaves ( and you are TOTALLY confident in the new PSU) I'd take a guess at a shot motherboard
Hope that helps a bit!