Eventhough I am a noob at ubuntu (only 4 days into it), i was faced with a similar delima 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.
Hope this helps.
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).