It's an issue with running on TVs that only support their native resolutions and not VESA ones. Bascially when we do auto-detection of the screen resolution at inital startup, we only try to detect VESA modes.
This is fixed in the upcoming patch, which will search all standard modes.
The simplest solution is to run with -window on the command line, then in the Options menu choose the resolution you want to use, accept the game, and quit out. Then start the game again without -window.
The command line ("Target") in the shortcut should look something like this:
"C:\Program Files\THQ\Company of Heroes\RelicCOH.exe" -window