O grub2 não tem um comando "grub", apenas o legado do grub tem isso. E o grub legacy não possui um comando grub-mkconfig, apenas o grub2 tem isso. Então sim, você tem duas versões do grub instaladas. Meu palpite é que você tem o pacote grub-common instalado, que contém o grub-mkconfig mas você não tem o pacote grub-pc que contém a maioria dos arquivos do grub2 e é necessário para o grub em um BIOS PC (se você tiver o firmware UEFI, você pode querer o grub-efi-amd64). Acredito que seja assim porque o pacote "grub" (contendo grub-legacy) e o pacote "grub-pc" (contendo a maior parte do grub2) conflitam e, portanto, não podem ser instalados ao mesmo tempo. Como você tem o grub legado instalado, o "update-grub" está modificando o /boot/grub/menu.lst do legado do grub, em vez de usar o grub-mkconfig para escrever um /boot/grub/grub.cfg.
A solução é simples:
Se você possui um sistema baseado em BIOS, basta instalar o pacote grub-pc
(que removerá automaticamente o pacote grub
).
Se você tiver um sistema baseado em UEFI, instale grub-efi-amd64
.
Se você não sabe o que você tem, diga isso em um comentário e eu vou ajudá-lo a descobrir isso.