Here are a few things to try:
1. Open the /etc/X11/xorg.conf.pluto file. Under the section "Device" there should be an option called "UseEDID". Change it from False to True. If your TV reports the correct timing information over DVI then that should help. If that works then you will also need to edit the /usr/pluto/bin/Xconfigure.sh file and add the line "exit;" at the top of the file. Each time you start LMCE it tries to regenerate the xorg.conf.pluto file so you will loose your changes.
2. If that doesn't work then try googling for "modeline + model of your TV". Chances are that someone else has figured out a Linux modeline for your TV. You can add your custom modeline to the /usr/pluto/bin/Xconfigure.sh file along with the other modelines. I haven't tried this myself, but I believe LMCE will attempt to use your modeline when it tries to configure your display.
3. If that doesn't work then try to get it working under Ubuntu. Run "Applications->System Tools->Nvidia X Server Settings". If you are able to configure the display to your liking then click on "Save to X Configuration File" and generate an xorg.conf file. You can then compare the xorg.conf.pluto file and the xorg.conf file and copy across the relevant information for your display. I don't think you can simply replace the xorg.conf.pluto file out right. There might be a few settings in there that are required by LMCE apps. Once again you will need to edit the Xconfigure.sh file like in Option #1.
Option #1 worked for me.
Also read this thread:http://forum.linuxmce.com/index.php?topic=1310.0
It's important that you are using the "nvidia" driver versus the "nv" driver or you will have problems later when your try to run the Orbiter.