Eu procurei este arquivo nos arquivos do pacote Ubuntu e descobri que ele fazia parte do pacote grub-pc-bin . Eu tentei instalar esse pacote, mas ele tinha dependências ruins.
No entanto, como eu sabia que precisava apenas desses módulos i386, acabei de fazer o download e descompactar o pacote, depois movi os arquivos manualmente assim:
cd /tmp
sudo apt-get download grub-pc-bin
dpkg-deb -R grub-pc-bin_2.02~beta2-36ubuntu3.16_amd64.deb grub/
sudo mv grub/usr/lib/grub/i386-pc/ /usr/lib/grub/
Agora você deve tentar novamente e deve funcionar.
(Observação: o comando apt-get download pode gerar um arquivo com uma versão diferente da mostrada. Se você receber erros na linha dpkg-deb , verifique se está segmentando o arquivo que acabou de baixar.)