Для начала должны быть установлены пакеты:

   sudo apt-get install build-essential cdbs fakeroot dh-make debhelper debconf \
      libstdc++6 dkms libqtgui4 execstack libelfg0 ia32-libs

Затем, нужен драйвер Catalyst и патчи к новому ядру:

   mkdir atifix
   cd atifix
   wget http://www2.ati.com/drivers/linux/ati-driver-installer-11-5-x86.x86_64.run
   wget http://www.mindwerks.net/wp-content/uploads/2011/03/2.6.39_bkl.patch
   wget http://www.mindwerks.net/wp-content/uploads/2011/03/no_bkl.patch

Распаковываем драйвер и применяем патчи:

   chmod +x ati-driver-installer-11-5-x86.x86_64.run
   ./ati-driver-installer-11-5-x86.x86_64.run --extract driver
   mv *.patch ./driver/
   cd ./driver/
   patch -p1 -i 2.6.39_bkl.patch && patch -p1 -i no_bkl.patch

После патчей устанавливаем драйвер:

   ./ati-installer.sh 8.85 --install

Более правильный способ установки, использованием штатного пакетного менеджера:

1. узнаём список поддерживаемых дистрибутивов:

   ./ati-installer.sh 8.85 --listpkg

2. генерируем установочный пакет для нужного дистрибутива из списка
   ./ati-installer.sh 8.85 --buildpkg YourDistrName

3. устанавливаем. к примеру, пакет для Debian

   dpkg -i fglrx*.deb


Если во время установки не всплыло никаких зависимостей, то выполняем

   aticonfig --initial -f

Перегружаем компьютер или X-Server и проводим на всякий случай диагностику:

   cat /var/log/Xorg.0.log | grep EE

После рестарта можно диагностировать с помощью

   fglrxinfo и fgl_glxgears