I have an HP Pavillion with a Radeon HD 4650 with 1600x900 resolution that I can hook up to a Sony Bravia with 1080p via HDMI. The picture looks good but is not full screen. In the CCC it gives me an option to "force" a resolution. Not sure if it's possible or wise to do so as I just bought this a couple of months ago.
I do the same thing with my desktop. Does your TV have different modes, i.e. cinema, normal, etc...? I had that issue at first, but after switching to cinema mode, everything is now in full screen. Give that a go.