I don't know what to say. I went with an nVidia card this time.
You gotta remember that CoV is an MMORPG, though, and therefore can suffer the severe effects of lag, making it seem like you're getting shitty performance when you're really not. WoW sometimes chugs on my machine, and then when I get a decent ping, it's smooth as silk.
Stuff like EAX can also fuck up your FPS.
The low test results are suspect, though... It's probably a driver problem more than hardware conflicts.