Já tive esse problema, rodei o CD de instalação, escolhi atualizar o ubuntu e funcionou.
Se não parecer essa opção (o que já aconteceu comigo também), aí a coisa tá feia mesmo, entre em Live CD salve seus arquivos em um pendrive ou HD externo ou em alguma outra partição do HD e reinstale. É raro, mas as vezes é preciso formatar o Linux... fato...