Hmm, when you first push the button, do the fans start at all? Do you hear the hard drive start?
It could be a faulty power supply, or another part that is not passing the startup test.
I'm only guessing, but the 500W should be enough. Most 500W with 2 pci-e connectors have okay Amp ratings.
I think I'd really like you to run some stress tests on your computer first. It has always been weird to me that you could game on the computer, and only had issues on startup.
Use Prime95 to test your cpu, and Furmark to test your video card.
|MG| Prime95 26.6 Build 3 Download
eithrf 32 or 64bit is avaliable
FurMark: VGA Stress Test, Graphics Card and GPU Stability Test, Burn-in Test, OpenGL Benchmark and GPU Temperature | oZone3D.Net
Theses 2 test will heat your compurter up pretty good, while urmark shows temperature of you video card, use coretemp to watch your cpu temp.
Use the stand alone which doesn't need to be installed.
Running these tests will max out your computer, and if your power supply isn't up to it, it'll crash or error out.