Well I found a couple things, but I doubt they'll help solve your problems.
I've tested on a system with an ATI card (5670 with an old CRT) and a system with an nVIDIA card (GTX 260 with a 1440x900 LCD) and on the nVIDIA system I initially had a problem using 1280x800. Attempting to change to that custom resolution just had the screen flicker and default back to 800x600. That doesn't really sound like what you two are describing, though.
In any case, I was able to get it to switch to 1280x800 by adding a custom resolution (1280x800) in the nVIDIA control panel. But seeing as how your native resolution is already 1280x800, I doubt that's your problem. If you want to look into it though you can follow the instructions in the third post of
this thread. I'm sure it has to already be a recognized resolution though, since I assume you've been using it.
I do not know off the top of my head how to add custom resolutions with ATI cards. I don't have the catalyst control panel installed on here at the moment, but it's probably somewhere in there.
Oh and the second thing I found is that hardware object rendering sometimes switched the resolution back to 800x600, so I guess make sure object rendering is set to software mode.
Besides that, I don't have too many ideas. 1280x720, 1280x800, and 1440x900 all seem to be working fine here.
Can you tell me what video card and game version you're using? I've been testing on the demo since I don't own the game, so if you'd like, you can download the
demo and try the fix with that version just to rule out the possibility that it's an issue with a specific game version.
I'd say perhaps it's a problem with Vista/7 (I know this game has a few problems with those OSes), but it would really be strange if it caused the custom resolutions to malfunction but not the originals.