Richard, xrandr me pediu o mesmo depois de atualizar para 12.10. Eu poderia resolver esse problema removendo meu driver gráfico proprietário instalado anteriormente ...
sudo apt-get remove --purge fglrx fglrx_* fglrx-amdcccle* fglrx-dev* xorg-driver-fglrx
... e usando o driver de código aberto padrão.
sudo apt-get remove --purge xserver-xorg-video-ati xserver-xorg-video-radeon sudo apt-get install xserver-xorg-video-ati sudo apt-get install --reinstall libgl1-mesa-glx libgl1-mesa-dri xserver-xorg-core sudo mv /etc/X11/xorg.conf /etc/X11/xorg.conf.bak
(fonte: link )
Desejo-lhe muito sucesso também.