O comando xfix ainda existe? Isso era usado no 7.04 se não me falha a memória.
De qualquer forma, não creio que reinstalando/removendo o pacote ubuntu-desktop vá resolver algo para o seu problema. Ele é apenas o pacote que coloca o splash image, monta o nome da distro e etc.
Eu começaria assim:
sudo X -configure
sudo cp xorg.conf.new /etc/X11/xorg.conf
startx
Se ainda falhar, tente usar o driver vesa ou até mesmo um VGA, apenas para você conseguir startar o video e ter uma máquina funcional enquanto tentamos drivers diferentes para esta sua Radeon.
EDIT
Esqueci de colocar um exemplo de xorg.conf com VESA funcionando :
Section "InputDevice"
Identifier "Generic Keyboard"
Driver "kbd"
Option "XkbRules" "xorg"
Option "XkbModel" "pc105"
Option "XkbLayout" "us"
EndSection
Section "InputDevice"
Identifier "Configured Mouse"
Driver "mouse"
EndSection
Section "Device"
Identifier "Configured Video Device"
Driver "vesa" # if vesa fails too, try replace "vesa" with "vga"
EndSection
Section "Monitor"
Identifier "Configured Monitor"
EndSection
Section "Screen"
Identifier "Default Screen"
Device "Configured Video Device"
Monitor "Configured Monitor"
SubSection "Display"
Modes "800x600" # if this fails, try lower resolutions like "640x480"
EndSubSection
EndSection
Section "ServerLayout"
Identifier "Default Layout"
Screen "Default Screen"
EndSection