Finalmente, encontrei a resposta.
update grub lançou milhares de entradas sem sentido no grub.cfg (o arquivo tinha ~ 16.000 linhas grandes!)
Após apagar o arquivo memtest86 + e uma imagem antiga do linux de / boot e rodar o upate-grub novamente, tudo ficou bem.
Embora eu não entenda o que estava acontecendo, o erro desapareceu.