If you have a 4mb card: Do you use 16bit?
Yes he does, that's what "Graphics 800,600,16" means. A 16 bit 800 x 600 display.It works perfectly here, although there is some rather serious banding issues due to the 16-bit display, it is however much less severe than in your screenshot.
I'm going to go with awful gfx-card and/or drivers.