Você estava executando atualizações através do "Software Updater" do Ubuntu? Tente executar "sudo apt-get update" e "sudo apt-get dist-upgrade" a partir da linha de comando. Eu acho que tive problemas semelhantes após uma atualização recente, que eu suspeito que seja devido ao Software Updater esconder alguns importantes avisos para o dubkg-reconfigure para o grub.