Eu tive o mesmo problema hoje. Iniciando o sistema pelo live cd eu descobri que no arquivo /boot/grub/grub.cfg havia listados os antigos kernels 3.19.0-16 e 3.19.0-15. Eu mudei isso para 3.19.0-26 e 3.19.0-25 e poderia, então, felizmente reiniciar sem quaisquer problemas.
Talvez este seja também o caso do seu sistema?