Comece com um livecd, abra um terminal
sudo fdisk -l
sudo mount /dev/sdax /mnt
sudo mount --bind /dev /mnt/dev
sudo mount --bind /dev/pts /mnt/dev/pts
sudo mount --bind /proc /mnt/proc
sudo mount --bind /sys /mnt/sys
sudo chroot /mnt
e agora você pode fazer update-initramfs e update-grub sem erros.
update-initramfs -u -k 2.6.38-8-generic (or your version)
Se você não conhece sua versão. Use:
dpkg --list | grep linux-image
E atualize o Grub.
update-grub2
Reinicialize seu sistema.