I also use KDE, so it's difficult for me to advise but if you go into your gnome-control-centre under the Hardware section you have "Graphics Card and Monitor" and "Screen resolution Options" make sure the resolutions indicated under each settings option is the same.

If you post back kindly provide details of your hardware, graphics card and xorg.conf settings. A screen shot would also be helpfull.