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
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.
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).