Já consegui resolver este problema.
Aqui fica a solução para quem quiser:
1. sudo apt-get install xorg-driver-fglrx
2. no xorg.conf em "Device", alterar o "Driver" de "ati", ou o que lá estiver para "fglrx".
3. startx, para reiniciar o X e está a bombar! :wink: