I had the same issue, but I think that it isn't monitor fault, cause of course every one will be able to display 800x600 resolution. Maybe it is because some drivers/graphic settings? I have 2x GTX 560 Ti in SLI mode ...
Anyway, I was able to play in window mode, just while the game starts and your monitor displays error message about resolution, hit ctrl+enter or alt+enter, that will force game to display in window. Then in settings select some other resolution, but do not select "full screen" option. This way works for me, and the only unplayable resolution is 1920x1080 which is my native operating system resolution ...
I know that this is a temporary fix, but at least it should allow you to play the game