tio, yo te recomiendo no usar ubuntu X64 y una X800 por que yo tengo exactamente esa configuración y... es una pesadilla, tendrás que hacer maravillas
La cuestión es que el entorno grafico peta por que ubuntu intenta configurar tu tarjeta con el driver "ati" y no puede arrancar el servidor.
Sin embargo si configurars el xorg.conf para que arranque con el driver "radeon" no deberías tener problemas, al menos a mí me funcionó
(si está con radeon, es al revés, pero ahora mismo creo recordar que era así)
Después si quieres instalar los drivers ati, tienes que bajarte alien y todos los paquetes para convertir rpm a deb, por que es necesario para instalar el paquete.
Usa el ati*.run no los rpm, instalatelo, haz un aticonfig sobre el xorg.conf, editalo y quita la extensión "composite" (es un consejo)
prueba ahora con el driver "radeon (fglrx)"
si lo haces todo nos vamos de birras.
pd: te recomiendo mandriva x86_64 con esa configuración, no es 64bits puro como debian/ubuntu, pero va rapido y no da tantos quebraderos.