Re: A final throw of the Minty dice before @Adam 52
The question we need to know is whether you have some esoteric or maybe cutting edge graphics card, or are maybe trying to use the proprietary binary graphics driver from AMD or Nvidia on an older graphics card..
For new high end cards from both Nvidia and AMD, the proprietary Linux drivers often lag the availability of the cards by some months, and the open drivers may not support the newer hardware until some bright spark works out how the API has changed.
There are also some obscure cards that there may not be drivers for in the Linux repositories, but this is rare.
What is more annoying is that the proprietary drivers are dropping support for older cards. I was caught out when I upgraded an LTS release on a system with an Nvidia fx7800 onboard that had the proprietary Nividia drivers loaded. After upgrading, I suddenly was down to un-accelerated 800x600 256 colour (i.e. basic VESA) rather than the 32 bit colour 1280x1024 that I was expecting. This sounds similar to your situation. I've had similar problems with older AMD/ATI cards as well.
The new release of the proprietary Nvidia binary had silently dropped support for the older chipset, leading to the lowest-common denominator driver being used. Unfortunately, the main way of removing the binary driver, which is required to get the open source drivers configured correctly, is normally written using dpkg from the command line. It is also possible from Synaptic (which is no longer installed by default), but is rather more difficult from the Ubuntu Software Centre (which seems to decide that removing software is something that users should be dissuaded from doing).
Unless you actually desperately need them, I would nowadays always suggest that you use the open drivers, and if you do use the proprietary drivers, switch back to the open drivers before doing a dist-upgrade.
Of course, this is not Linux's fault (if Linux can actually have fault attributed to it). It actually shows up a fundamental support issue with the companies that produce PC hardware without a full commitment to Linux. This should even extend to the obsolete chipsets IMHO, because Linux is very often deployed on old kit. Companies should either fork their proprietary drivers and leave the old ones in the repositories so you can keep using the old drivers without having to hold them back (and don't get me started on this, it has huge problems), or open-source the drivers, or even just the full API for the cards they deem obsolete to allow the community to support the cards without having to reverse-engineer the chipsets.