First off, set your resolution to your monitors' native rez. 1920x1080 perhaps?
Now, it sounds like you just need to adjust the scaling. For some strange reason, ATI default has 15% underscan enabled.
Go to your Catalyst Control Center, select displays from the drop-down list. You should have a window with a large representation of the screen, and just below that there should be a smaller representation of your TV/monitor. Right-Click on that bottom small representation of your TV/monitor and then select 'Configure'.
You will now have a window with scaling options as one of the tabs. Go there and move the slider to get rid of the black bars.