I have not used this application, but apparently you can do that (and much more) in SwitchResX, available here: http://www.madrau.com/indexSRX4.html
On this page it says that "SwitchResX can also block unused resolutions": http://www.madrau.com/functions/custom/custom.html, and since the software allows to create display settings for individual applications (described here: http://www.madrau.com/functions/app/app.html), maybe you can even disable certain resolutions in that game and other relevant apps only.
SwitchResX is shareware and costs 14 USD. You can try it for free for 10 days.
If you want to disable available resolutions manually, edit this file
/System/Library/Frameworks/IOKit.framework/Versions/A/Resources/IOGraphicsProperties.plist
In there is a section that looks something like this:
<key>gtf-resolutions</key>
<array>
<integer>640</integer>
<integer>800</integer>
<integer>1024</integer>
<integer>1280</integer>
<integer>50332928</integer>
<integer>67110144</integer>
<integer>1344</integer>
<integer>1400</integer>
<integer>1600</integer>
<integer>1920</integer>
<integer>100665344</integer>
<integer>2304</integer>
</array>
These are all widths, the height is calculated by the system. You cannot delete the maximum resolution, it is not listed in this file but comes from the monitor itself.
Add or delete resolutions from that section.
I have not tried this myself, and you are doing it at your own risk.
Note: To edit this file, you must either be logged in as root, edit it using sudo in the Terminal and a terminal-based editor such as vi, or use an editor that unlocks the file for you such as TextWrangler. Or, and this might be the best way, copy the file to the Desktop, edit it, and then drag and drop it back to the correct location holding down the Option key (you will be asked for your Admin password).
It might be a good idea to create a backup of the original file before you make any changes.
I'd recommend the Plex approach, not the Airplay solution. If you can handle the jailbreak (ATV2 only!), it's the best approach out there for non-iTunes movies on your ATV. And, I hate to say it here, consider the Roku, which is really cheap, officially supports Plex, and should be able to play anything you throw at it.
Best Answer
I solved it. After setting up a remote connection, I went through the video settings and it turns out the only resolution supported was 720p. It was, by default, using something else that didn't work.