I'm pretty sure it's not a bandwidth issue. It's most likely just an issue of that specific monitor or video card, more likely the monitor.
My 19" monitor is crystal clear at 1024x768, but starts to get slightly blurry at 1280x1024, and is unusable for long periods of time at 1600x1200. Some monitors can do 1600x1200 fine on vga, though.
It can actually be the strength of the signal. A good cable gives far better quality than a crappy one. A relatively short cable also gives better quality than an extended one.