1360*768@60 Hz (and a few others, don't remember exactly which - 75 Hz is one, I think) is WXGA - standard is a matter of definition these days, since all modern graphics cards support any resolution that is a multiple of 16 and many support even more than that, but at least it has a name. If the native resolution of the screen is 1366*768 (which is common for 37" LCDs), 1360*768 is the closest you'll get without breaking the multiple-of-16 rule. Another option which both TV and GPU should support is 1280*720 - 720p. I have used both from a Mac.
VGA ports can be used for any resolution, but the quality will eventually decrease if you use a too high resolution or too high refresh frequency. That level is way over XGA or WXGA though - I don't know what XVG is. The standard that has a real upper limit is single link DVI, which supports up to 1920*1200@60 Hz after which you have to use a double link connector.
I would strongly recommend that you try a DVI-to-HDMI cable again, set the display to "PC standard" (sometimes you can reset the ports from set-top box to PC and back again), shut everything and start it new, with the TV first. That should show your resolution again.
If that also fails, try an application called
SwitchRes and either connector. That should force the GPU into the right resolution.