FGLRX on legacy graphics cards
So, you tried to upgrade the AMD Catalyst drivers on your Linux machine and you lost your graphics. Do not despair! There is still hope.
This tutorial applies to those who have an AMD Radeon HD 2XXX to 4XXXX.
If you're using Xorg 1.13, it will, unfortunately, require you to downgrade to 1.12. But that should be easy enough and you can live with that.
As more information is gathered on how to do it in more distributions, this page will be updated. For now, you'll have the Ubuntu tutorial, but a Gentoo tutorial is predicted to arrive soon enough.
Downgrading the Xorg and installing the driver under Ubuntu has become relatively easy, thanks to Tomasz Makarewicz, who provided the community with a PPA for that effect.
If you attempted to have them running under Ubuntu 12.10 (Quantal Quetzal) you got punked.
Tomasz's PPA has everything you need. Just fire up your console and issue the following commands:
sudo add-apt-repository ppa:makson96/fglrx sudo apt-get update sudo apt-get upgrade sudo apt-get install fglrx-legacy
You can now restart your computer and when it becomes alive, you'll have your graphics back, with Xorg 1.12.4 (this PPA downgrades it for you) and Catalyst 13.1, which was released on the 21st of January 2013 (<=> FGLRX 188.8.131.52).
Special, kernel 3.5.x
For kernel 3.5.x, you may have to pay attention to the instructions on the 14th comment on this link and apply the said patches: 
Special, kernel 3.7.x
On kernel 3.7.x, you will most likely need to manually edit the driver code and install it with DKMS.
After doing the PPA installation steps, you'll have the driver code installed under /usr/src/fglrx-legacy-184.108.40.206/
Find the firegl_public.c, edit it and add the following line somewhere on the top of the file:
#define VM_RESERVED (VM_DONTEXPAND|VM_DONTDUMP)
The VM_RESERVED symbol was removed on kernel 3.7.x, so, if you try to compile the module without this patch, you'll have undefined reference errors.
Now, you need to compile and install the module. Once again, fire up the command line and issue the following:
dkms install fglrx-legacy/220.127.116.11
Reboot and you're done.