Originally Posted by TheGamefreak
Alright, so basically up the voltage or down the clocks
I would definitely up the voltage and check for stability. Downclocking would be counter-intuitive, as you would only downgrade the performance of your GPU.
Once you can verify you have a stable OC via ATI Tools and some benchmarks (Heaven 2.5, 3dMark11, etc), then see if the issue persists. I'm guessing (hoping) it won't.