As shown in the image, any monitor connected to the HDMI output (direct HDMI to HDMI) will shrink to the center of the screen, and a black border will appear around it.
The border can be manually removed by opening the AMD Catalyst Control Center with Administrative privileges and setting the Overscan value to 0%.
(Go to Preferences > AMD Catalyst Control Center > edit page for the HDMI monitor > Adjustments tab, and look for the Scaling Options panel. Set the slider to 0% Overscan.)
The problem is that Catalyst forgets this setting upon the next reboot and requires that you manually adjust it again and again to get a proper picture. Adjusting other settings, such as the Image Options or vertical refresh rate, have no effect either. Catalyst stubbornly refuses to remember the current settings.
There is a command line solution as discovered on this link. It also works in Ubuntu 10.10, and it is repeated here for convenience.
Open a terminal and enter a single line,
sudo aticonfig --set-pcs-val=MCIL,DigitalHDTVDefaultUnderscan,0
Reboot the computer, and the HDMI image fills the screen properly without any black borders.