I was faced with a similar dilemma when I hooked up my pc to a Philips 42" LCD (model 42PFL5704D/F7). You can have it set up at at that resolution (i have mine at 1920 x 1080 - and it's great.
To do that you need to install the proprietary drivers from Nvidia. Simply open the terminal and enter the following commands, one line at a time:
sudo add-apt-repository ppa:ubuntu-x-swat/x-updates
sudo apt-get update
sudo apt-get install nvidia-current
The reason being that the latest drivers has not yet made it to Ubuntu's repositories.
Note 1: I think the resolution you were going for is 1360x768.
Note 2: Make sure your tv is setup to unscaled (Menu > TV Settings > Picture > Unscaled).