Eu tive muitos problemas com a atualização das versões do ubuntu. Eu recomendo que você faça apenas uma instalação limpa e não uma atualização. Ele vai fazer isso correto.Eu tinha 12,04 e atualizei para 12,10, mas tudo dá errado. Agora eu acabei de instalar o 13.04 e tudo funcionando bem.
Tente.