ander, you and I are in quite the same boat. I noticed when I first got my FX5600 Ultra that it was *made* overclocked. I have to reduce both my default core and memory speeds for it to be stable. See this thread about nvclock:
The newest NVClock build will "support" your card - I use the term loosely since it doesn't quite work with mine. If I change the memory speed, everything turns to poop.
Since I've been through the rigamaroll with this, if you have a question regarding configuration, I may be able to help.