Often times, games perform at different resolutions and "force" or adjust the graphics into the native resolution that the game's settings are on. So if the game's highest resolution is lower than 1920x1080 - which I imagine most are - it may be putting the computer into a lower, unsupported resolution.
Try to find a resolution that the game can be shown in that the televison also accepts.
I hope someone can help. I have a samsung LE40A556P1F LCD TV
When I connect my PC to it everything works no problem until I load a game and then I get "MODE NOT SUPPORTED"
The TV supports 1920x1080 res @60Hz which my PC is set to. My Graphics card is a ASUS Nvidia 8800GTX with DVI out put which I have connected to the TV with a DVI to VGA cable.