Oh my God!! Why didn't you tell that before? It is the PSU. I have had similar issues in the past with my 5870 Crossfire. Sudden restarts for a prolonged period and then the PSU just died on me one day. It's got to be the PSU. Two things before buying a new PSU:
1. Make a rough estimate of your power consumption( CPU tdp+ Motherboard tdp(20-75W)+GPU tdp(500W in your case) and then find the total to have an idea of your peak consumption( roughly 750W in you case).
2. Always check whether the PSU is 80 PLUS Bronze certified. 80 PLUS Gold/Platinum are better and costs more..
And also 3rd class brands of PSUs fail to deliver the marked wattage output as indicated on the sticker. Cooler Master is not a good brand for PSUs. Check this review of another Cooler Master PSU and you will know:http://www.hardwaresecrets.com/article/Cooler-Master-eXtreme-Power-Plus-600-W-Power-Supply-Review/1034