X-server setup

Hi, We're having problems when users connect to a Suse linux box when they run Xwindows remotely. They're complaining that the display (background) is grainy, looks like its missing colors. When I check the display on the console it is fine (they agree). I ran SAX2 and did the configuration which I set at 1280x1024 16bit color and 85 Hz refresh. So it seems that the hardware is fine, the problem is somewhere with the remote display, ie not enough resolution/colors are getting there. Any suggestions? Thanks ALex