I'm using an ATI Radeon 6570 and my monitor's native resolution is 1440x900. I've got Portal and the game runs fine, but it has two huge black bars on the side. The in-game configuration doesn't have this resolution. All other resolutions still give me black bars. All other games run fine.
I spent a lot of time searching the 'net and they all seem to suggest the same thing: Go to the Catalyst Control Center and go for the Scaling option.
It is either you are not at your native resolution when you have the black bars, or it's a scaling issue, which can be adjusted in the CCC. I don't have CCC installed right now, so I can't step you through it.
I too reached the conclusion that the bars could be fixed with Scaling, as indicated by several tutorials. But as I mentioned, all of the tutorials are based on an older version of CCC, and the instructions don't tell me how to find the Scaling options in the new overhauled CCC interface.