I have a PowerColor 3870, and I have no problems at all.
Anywhere between 300 and 450 fps at 2560x1600 32 bit, depending on the view.
The CPU is overclocked, but the graphics card isn't ...
I'm using the latest 7.12 drivers, under Windows Vista Ultimate 64 bit.
Did you uninstall all the old drivers (nVidia or ATI) before installing the 7.12?
Tried closing all the programs open apart from LFS? Defrag? etc etc.
Tried updating other drivers in your system, sound, chipset, etc?
Try checking the settings in Catalyst as well, if you'd altered something, put it back to default.