Since you've explored the video card driver avenue, I'm inclined to think it may be how Windows 7 is seeing / using your external monitor (TV in this case).
What "mode" are you having Windows 7 output to your monitor? Are you extending the desktop, duplicating the desktop onto the TV or having the desktop displayed only on the TV?
I ask this because what may be happening is that your laptop display may be trying to send it's native resolution to the TV which may be unsupported by the TV so you are getting an unsupported mode message on the TV. What does Windows 7 detect your television as? Guessing a PnP display/monitor?
I would try extending or mirroring it first so that you can still see your desktop on the laptop screen and then go into the Windows Display settings (right-click on desktop, choose Display Settings). You should be able to choose the TV (External Display) and adjust the resolution there. You may also want to look in the advanced options to see if there is a refresh rate control. If so, you'll want to ensure the refresh rate for the TV is set to 60Hz.
Keep in mind that your laptop may not be able to drive 1920x1080 to your TV and drive your laptop display at the same time at it's native resolution. So, you may only get the full display on your TV when Windows is set to display the desktop on ONLY the TV. Are you also choosing the output to TV using the laptop output display key combination (like Fn-F5 or something)? Or are you using the Windows+P shortcut?
If none of that works you may need to select a custom monitor display driver for the TV (not sure what it currently shows up as) or, barring that, you may want to take a look at a tool like PowerStrip to build a custom resolution and see if that will work.
Apologies if you've tried all those things...Hope at least some of that helps. :)