Parece que o arquivo de configuração do grub não foi gerado corretamente.
Você não precisa reinstalar o grub, mas o comando para isso é:
sudo apt-get grub-install /dev/sda
Você definitivamente precisa atualizar a configuração do grub:
sudo apt-get update-grub
Isso deve remover a entrada antiga.
Se isso não acontecer, você poderá ter kernels antigos ainda em /boot . Existem várias respostas sobre como remover os kernels antigos, se necessário.