Don't forget to change your TV's Video Input. This is usually done with a button on the Remote Control (commonly labeled "Input". Switch to the proper HDMI input.
If you've already done this, you may need to enable HDMI output through the ATI Catalyst Control Center.
As Wolfshadw already stated, make sure you set the desktop resolution on your PC to the "Native Resolution" of your TV. This will ensure the best picture quality, as well as compatibility. Otherwise your TV's image/video processing chip will alter the size and shape of the picture on it's own. This doesn't always work out well.
720p = 1280 x 720
1080i = 1366 x 768
1080p = 1920 x 1080