Entra en modo Live, guárdate a otra partición o HD los datos que necesites y reinstala Ubuntu en limpio formateando la partición. Creo que es la solución que menos quebraderos de cabeza te va a dar.
Yo solo recomiendo actualizar si es de una versión a la siguiente (8.10 a 9.04, o de 9.04 a 9.10) y solo si no se ha usado apenas repositorios externos. Yo cuando salga la 10.10 aun estando con la 10.04.1 creo que lo hare en limpio (he tocado un sin fin de cosas y aprovechare para hacer algunos cambios de HD y particiones)
Tu has subido 3 o 4 versiones del tirón y tenias un montón de posibilidades de que te diera problemas, ya que los cambios han sido notables de una a otra. (no te habrá quedado ni un solo paquete sin tener que actualizar...)
