Отключил compiz (я правильно понимаю, это System>Preferances>Apearence>Visual effects>None ?)
Совершенно верно.
После этого видео тормозить перестало совсем. Но без compiz стало грустно.
Модуль иксов DRI не может с достаточной производительностью одновременно рендерить OpenGL приложение (compiz) и обрабатывать видео. К сожалению пока выбор: либо жить с тормозящим видео, либо без compiz. И ждать новых драйверов от ATI с поддержкой DRI2.
Похвальна твоя доскональность в изучении вопроса. То, чем могу помочь касаемо чек-листа:
Kernel module build environment . Kernel source code includes either the Kernel Source or Kernel Headers packages
Поищи пакеты linux-headers - это заголовки ядра.
aptitude search linux-headers
The RPM utility should be installed and configured correctly on your system, if you intend to install via RPM packages ATI CatalystTM Linux Installer
Ubuntu - Debian-based дистрибутив. Использует пакетную систему deb (dpkg). Драйвера будешь ставить либо пакетом из репозитория, либо *.sh инсталлятором с сайта ATI.
Да, RPM тут не при чем.
POSIX Shared Memory (/dev/shm) support is required for 3D apps
GNU/Linux - полностью POSIX-совместимая система. Не бери в голову - все нормально.

glibc version 2.2 or 2.3
Странно. Должен быть виртуальный пакет glibc. Glibc - это библиотека процедур языка C. Должна быть (иначе система не работала бы

) Поищи пакет libglib.
XOrg 6.8, 6.9, 7.0, 7.1, 7.2, 7.3 or 7.4
Очень часто возникает путаница. Протокол обмена x-window имеет версию 11, но сам сервер имеет свою версию. Полная версия иксов выглядит X11R7.4.
Все нормально. У тебя либо 7.3 (Ubuntu 8.04), либо 7.4 (Ubuntu 8.10).
Xfree86-Mesa-libGL
Не уверен, но, имхо, это одна из библиотек иксов. Должна быть установлена по умолчанию.
freetype
Опять же не уверен, но freetype по умолчанию должен быть. Это стандартный формат шрифтов.
zlibg1
Да, это то, что нужно. Библиотека сжатия.
Create a central location for your ATI Proprietary Linux driver downloads
ИМХО просто выпендриваются. Имеется в виду сложить все скачанные драйвера в одну папку.
Uninstall any third party graphics driver such as NVIDIA proprietary Linux graphics drivers currently on your system;
Смысл этого предложения мне не понятен. Последний идиот не станет ставить драйвера NVIDIA при видеокарте ATI.
ATI recommends you uninstall the ATI Proprietary Linux Driver before installing a newer version
sudo sh путь к установщику 8.54.3 версии --uninstall
если ставил из sh инсталлятора с сайта ATI.
Если из пакета, то надо удалить этот пакет. Как называется, не знаю.
aptitude search ati