Didnt somebody have a post not too long ago about the ATI control panel itself causing problems? Might want to do a search on that.
I'm sure you have your specs posted somewhere and they are sufficient. These settings help most people having issues. After you try them then you can narrow down your problem area. (I am using what I know from Nvidia's setups, I'm going to assume that since most of the terms are interchangeable that yours will be called the same thing).
Do you have Anti Aliasing off or at least Application Controlled? I'd turn it off until you see if you notice a diff. If not, then turn it to App. Control. How about Anisotropic Filtering? Turn it off, then if there is no difference, turn it to application control. Now Vsync. Try turning it off (if you have it on). If you notice a big jump in your framerates check your monitor refresh rate and turn it up, then turn Vsync back on. Are your frame rates better than they were before? I'm not sure how high your system will support on the refresh, but the higher the number the better. If you dont find any of this helpful, check out this thread. Especially if you use WinXP. I'm not going to go into explaining why, you can read it and download the "fix" if you need it.
http://www.natural-selection.org/forums/index.php?act=ST&f=18&t=34027One other thing, is memory. Add more RAM, your system runs better and beleive me, it helps your fps. I went from 512MB to 1GB and I added 20 fps in the air. Anywhere from 5-10 fps on the ground.