I had the same problem : 800*600 only on a new laptop and I searched in the
laptop hardware description to find the brand name of the video card and chips
then I googled that brandname and eventually could download the specific drivers
from the manufacturer web pages. It was not too hard to do and now it works
perfectly, my laptop is Windows XP - Ubuntu Karmic 9.10 dualboot but I mostly
use it on Linux as I am much more satisfied with Ubuntu.