A partir da discussão nos comentários, a solução foi instalar grub-pc-bin
sudo apt-get install grub-pc-bin
A maneira de identificar o pacote que faltava era pesquisar os arquivos no link
Na seção "Pesquisar no conteúdo de pacotes" usando nomes de arquivos.
% bl0ck_qu0te% Como alternativa, você pode instalar e usar apt-file
para pesquisar arquivos em busca de arquivos, mas normalmente leva mais tempo do que uma pesquisa na Web.
sudo apt-get install apt-file
apt-file update
Pesquise em quais pacotes de arquivo (s)
apt-file search file_name
Neste caso, a partir da mensagem de erro
apt-file search efiemu32.o