I think this is about the hard limit when it comes to the resolution you can use. There was a thread some time ago where Hooman (I believe) mentioned, that the game crashes and/or slows down on very, very high resolutions. But the game can handle some resolutions higher than 800 x 600 (im running it on 1680 x 1050 just fine), I just don't know how to help here. Maybe you can try slowly scaling the resolution up beginning with 800x600 to find out how high it can be turned.
Is this a problem that only occurs in multiplayer? I'm asking because of the title.
Edit: It was probably BlackBox who told about this.