update-grub apenas atualiza as configurações do grub; você geralmente precisa executar grub-install depois disso.
O sistema não está inicializando, porque o grub ainda está apontando para o kernel antigo e não para o novo.
Se você tem grub no seu MBR, deveria ter sido então:
sudo update-grub
sudo grub-install /dev/sda
Assim, aconselho a inicializar o sistema / VM a partir de um DVD / pen / imagem do sistema ativo, como o Knoppix, e fazer o grub-install