A solução para mim foi (e provavelmente para qualquer um que tenha esse problema):
Inicialize no live cd e digite no terminal (é claro que você deve editar as operações de montagem respeitando sua própria tabela de partições):
sudo apt-get install grub-efi-amd64
sudo mount /dev/sda3 /mnt
sudo mount /dev/sda1 /mnt/boot
sudo grub-install --root-directory=/mnt /dev/sda
Agora o grubx64.efi deve inicializar sem problemas.
Executar o update-grub enquanto inicializado no ubuntu restaurou a aparência mais atraente do menu de inicialização do grub.