Acabei de encontrar uma solução hoje, ela não está relacionada ao BIOS / UEFI, mas sim à interface gráfica / não gráfica do usuário: Basta desativar a interface gráfica do GRUB2 e ela funciona.
Etapa 1: edite o arquivo /etc/default/grub
(como superusuário), adicione (ou remova o comentário) a seguinte linha
# Uncomment to disable graphical terminal (grub-pc only)
GRUB_TERMINAL=console
Etapa 2: Atualizar o grub
sudo update-grub