Eu enfrentei um dilema semelhante quando conectei meu PC a um LCD Philips 42 "(modelo 42PFL5704D / F7). Você pode configurá-lo nessa resolução (eu tenho o meu em 1920 x 1080 - e é ótimo. Para fazer isso você precisa instalar os drivers proprietários da Nvidia. Basta abrir o terminal e inserir os seguintes comandos, uma linha por vez:
sudo add-apt-repository ppa:ubuntu-x-swat/x-updates
sudo apt-get update
sudo apt-get install nvidia-current
O motivo é que os drivers mais recentes ainda não chegaram aos repositórios do Ubuntu.
Nota 1: Acho que a resolução que você escolheu é 1360x768. Nota 2: Certifique-se de que a sua TV está configurada como não escalonada (Menu > Configurações da TV > Imagem > Sem escala).