Verifique se grub-legacy
ou grub-legacy-ec2
conseguiu ser instalado em algum momento. Se eles fizeram isso, eles estão atualizando o antigo config menu.lst, mas o seu setor de boot está iniciando o grub2 e olhando para o grub.cfg para sua lista.
Para corrigir isso, basta reinstalar o grub2:
sudo apt-get install grub2
sudo update-grub
Então ls -l /boot/grub/grub.cfg
deve mostrar uma data modificada de hoje.
Teste a reinicialização durante uma janela de manutenção apropriada para garantir que ainda esteja funcionando corretamente.