I did install grub-legacy at some point but removed it almost immediately. I have reinstalled the grub-pc package and done everything to make sure it's a clean install not mixed with grub-legacy. It seems to be so.Are you making all the changes that have been suggested? In short: In /etc/default/grub add GRUB_GFXPAYLOAD=keep on the line after GRUB_GFXMODE=<resolution> In /etc/grub.d/00_header add if [ "x${GRUB_GFXPAYLOAD}" = "x" ] ; then GRUB_GFXPAYLOAD=640x480 ; fi on the line after if [ "x${GRUB_GFXMODE}" = "x" ] ; then GRUB_GFXMODE=640x480 ; fi In /etc/grub.d/00_header add set gfxpayload=${GRUB_GFXPAYLOAD} on the line after set gfxmode=${GRUB_GFXMODE} Run update-grub or update-grub2
This could mean your grub install is somehow broken, try to renew it from scratch, not mixing both grub-pc ("grub2") and grub-legacy. Or maybe you have typos somewhere in the variables so that they are not picked up by update-grub (you can also call "grub-mkconfig -o /boot/grub/grub.cfg" for grub-pc).