Comment 24 for bug 699802

I was finally able to workaround the problem here.

The script /etc/grub.d/00_header does some font path detection stuff and if that fails it doesn't set any gfxmode (neither the default "auto" nor anything defined manually in /etc/default/grub).

The font path is /usr/share/grub, but I have a separate /boot partition and the script doesn't seem to know how to handle this situation correctly, leaving me without fonts and gfxmode.

So, I just copied /usr/share/grub/*.pf2 to /boot/grub and ran update-grub again. Voila, I got my gfxmode and a working unicode font, too.