PSU is always the first thing to try because they fail pretty frequently and they are the easiest and cheapest thing to replace. Until you do a proper test i.e. with power to the 4-pin socket as well as the ATX 20-pin, you have not ruled it out.
You might just want to look here
and take a look at the pictures of some bad motherboard capacitors. Then look carefully at your own motherboard capacitors -- use a flashlight if necessary. If you see bulging caps, you know where the problem lies. If the motherboard caps look okay then the PSU is the prime suspect.
Rather than buy a new PSU you could try to find an adapter for the old one you have in there now. There are adapters available that will allow you to use an older ATX PSU with a newer ("Pentium 4 style") motherboard. Basically they have a hard drive power socket on one end and the square 4-pin P4 plug on the other. There's a picture here
. You might be able to track one of these down locally, but I couldn't find one listed on CompUSA's website. You could call around to some "mom & pop" type shops, they might have one.
If you do get a new PSU, make sure the amp ratings for +12V, +5V, and +3.3V at least equal the original power supply that came with your computer.