FGLRX won't install: Unable to correct problems, you have held broken packages

Unfortunately this is due to a bug in the latest updates to Ubuntu 14.04 and 12.04:

apt-get fails to install fglrx or fglrx-updates in 14.04.2 and 12.04.5

To fix it:

1. Remove the hardware enablement stack

   • Ubuntu 14.04 (tested and confirmed working):

     sudo apt-get install --install-recommends xserver-xorg libgl1-mesa-glx libegl1-mesa-drivers
     

   • Ubuntu 12.04 (untested):

     sudo apt-get install --install-recommends xserver-xorg libgl1-mesa-glx
     

   For some reason I had to run it twice since the first time returned an error.

2. Clean up extra packages

   sudo apt-get autoremove
   

3. Install fglrx

   sudo apt-get install fglrx
   

4. Reboot