When I connect my laptop to my HDTV by HDMI, the image on the TV is centered but is not full screen or even close to full screen. I set the resolution of both to the highest it can go and it still didn't work..?
Sounds more like a setting on your TV than the laptop. You should be able to switch between things like widescreen, super zoom, normal and different aspect ratios on your TV. Try flicking through them to see if you get a better fit.