Reinicialize e pressione a tecla Shift até o menu Grub aparecer. Em seguida, role para baixo até Opções avançadas para o Ubuntu. Role para baixo até um kernel antigo sem a opção upstart ou recovery e veja se ele irá inicializar.
Então você pode sudo apt-get install --reinstall linux-image-generic linux-headers-generic
e ver se funciona depois de uma reinicialização normal