Check the powersupply fan. I had this happen to me once. I had to often press the power button 5 or 6 times before it would start. The fan sounded fine, and some air was being moved, but the powersupply wouldn't start up. I eventually decided to open up the PS. Inside the fan was a small piece of metal that must have fallen in. This metal caused the fan to spin slower than it should, thus the PS thought it would overheat and wouldn't start the computer. I removed the metal (and replaced the fan just for safety) and everything worked again.
Its a long shot, but it is a quick and easy thing to check and a replacement fan is just a few dollars.