Acabo de instalar la NUEVA version de los drivers de ati siguiendo las instrucciones de la misma web que has puesto (de flavio stanchina) y van de lujo ^_^
A ver, si estas como superusuario (root) no uses fakeroot; simplemente el make-kpkg. Y ten en cuenta que debes tener los paquetes requeridos
apt-get install debhelper kernel-package libqt3-mt-dev xlibs-dev fakeroot rpm wget
Como digo, despues de tener los requisitos exigidos, he hecho el make-kpkg y modprobe fglrx y he cambiado en el XF86Config-4 los drivers "ati" por "fglrx" (todo como root, usando su) y al reiniciar las X he probado con el tuxracer y va genial.
Saludos!
PD: Por fin, despues de mucho intentar lo he conseguido.
PD 2: Por cierto, los nuevos drivers tiene soporte para X.org, x86_64 y para tarjetas X800 (eso es de lo mas destacado).