500w will be fine, no problem.
Ran a 580 on a 520w ocz psu fine for ages. no issues there
I'd be inclined to change to something with a better reputation. OCZ aren't bad, but they aren't the greatest.
What model though? It may have had more power on the 12v.