Well ... the 500W power supply SHOULD be more than ample for this system ... but the symptoms you've described are EXACTLY what you would see with a power supply that's having problems supplying the spinup current for your hard drives ... so notwithstanding the rating, I'd suspect the power supply is the most likely "culprit" here. The reason it behaves as you've noted is simple: Hard drives draw MUCH more power when they're initially "spinning up" (just starting to rotate). [That's why most RAID controllers support "staggered spinup" ... where there's a short delay between the spinup commands to the hard drives.]
Assuming that's the problem, what's happening is simple: When you "punch" the on button, the power supply can't quite supply enough current for all the drives to spin -- but each time they start just a bit ... and eventually they're not drawing a full startup load (since they're already in motion) => so the system starts.
Not the only possibility ==> but certainly the most likely.