Estaba revisando tu config y comparando con la que yo tengo. Todo más o menos igual. Lo único que veo, es que hay una opción que no tienes y que quizás podría funcionar. Sería añadir esto:
# Uncomment to disable graphical terminal
GRUB_TERMINAL_OUTPUT=console
No es que sea lo mejor, pero quizás al forzar el modo texto se vea siempre el menu.
Recuerda ejecutar sudo update-grub después del cambio.