Ahh, I had this problem with HDMI and my XFX 6870, if you are talking about the black borders. The scaling options didn't help me unfortunately. They may help with you though.
If underscan/overscan doesn't help. You may have to switch to using a dvi cable, as I did. It fixed the problem completely. It's quite a common problem with AMD cards and HDMI, usually involving Samsung TV/monitors, as it was in my case.