Si tiras de ubuntu, el proceso que has de seguir es tan simple como el siguiente:
Lo primero, cuando te aparezca el error de que no se inicia el servidor de las X, pulsa Ctrl + Alt + F1, logueate con tu usuario y contraseña, y escribe todo lo que va precedido de "#":
#sudo aptitude install xorg-driver-fglrx linux-restricted-modules-$(uname -r)
#sudo nano /etc/X11/xorg.conf
Busca la sección donde pone:
Section "Device"
Identifier "ATI Technologies, Inc. Radeon X700"
Driver "ati"
....
Donde pone "ati" cambialo por "fglrx"
Después pulsa Ctrl + X, y entonces confirma que deseas guardar (sin alterar el nombre del archivo).
Tras esto ejecuta lo siguiente:
#aticonfig --initial
#aticonfig --overlay-type=Xv
Vuelve a editar el /etc/X11/xorg.conf
#sudo nano /etc/X11/xorg.conf
Y añade al final del archivo lo siguiente (:
Section "Extensions"
Option "Composite" "Disable"
EndSection
Section "ServerFlags"
Option "AIGLX" "off"
EndSection
Y nuevamente guarda haciendo Ctrl + X.
Pulsa Ctrl + Alt + Retroceso (tecla Back Space o de borrar, según lo prefieras). Y en principio debería de lanzarse el xserver y te apareceria el login de gdm donde solo tienes que poner usuario y contraseña.
Si aún tras seguir esos pasos tienes algún problema, comentalo detalladamente.
Saludos
PD: Ten cuidado con las comillas dobles, procura no copiar pegar, es preferible que lo copies a mano (comillas incluidas).