Unknown power issue?

I have a homebuilt AMD 939 system I have been using for about a year and a half. The specs are as follows:
Coolermaster Centurion case
Asus A8n-SLI Deluxe mb
Antec Neo HE 500 w psu
Opteron 170 @ 2.8 ghz
Corsair twin x ddr 2 x 512 dual channel
Asus Geforce 7600gs graphics card
Thermaltake "Big Typhoon" cpu cooler
Thermaltake northbridge heat pipe cooler
2 Samsung 160 gb sata hard drives (dual boot w/ Ubuntu & XP)
DVD RW drive
front bay floppy/card reader
I originally had an Antec "smartpower" 500w psu which failed. They sent me the Neo He as replacement (the model I had was discontinued). Since replacement, I have been having is this; my computer would run fine for long periods of time, and if re-started (not shut down) it did fine. However if I shut down and tried to re-start, it would take several (as much as 5) pushes of power button to get it to fire up. Prior to starting it would try to start (ie. fans and drives would all try to start running) and then it would just quit. It would usually start on the 4th or 5th try. Then yesterday I shut it down for routine cleaning with duster spray, afterwards it would not fire up at all. I do not have the expertise to test the psu, but I am suspecting maybe it is the issue. What would be the best way to proceed in diagnosing the problem? I don't want to assume it is the psu. Could something be damaged due to previous psu failure? Any suggestions would be appreciated.

Thanks for the reply. I don't know why I didn't try that. I did have to do that with another case before. I can't get at the switch itself because it is inside of a molded protrusion in the front bezel of the case and they secured with a large blob of some type glue (possible hot glue). I will try switching power and reset leads on the motherboard headers, and post the results.