This is an annoyance I've had with Xen Linux guests for a while. The symptoms are: when booting in EFI mode, GRUB appears normally, but after the initial messages about loading the kernel and initramdisk, the screen looks like this:
After a while during the boot the screen eventually becomes normal before the login script. This is a small annoyance, except if the system drops into an emergency shell and you can't read the screen.
Debian's GRUB configuration in /etc/default/grub has an option GRUB_GFXMODE, I uncommented that and set the 1024x768. I observed the framebuffer to be a bit more readable, but still garbled. Since the resolution was correct, I assumed it has to do with color depth and tried setting the color depth too, which wasn't instantly obvious in the configuration file examples.
But in my case setting GRUB_GFXMODE=1024x768x32 finally made it look normal right from the start.
I determined the resolution and color depth from virtual_size and bits_per_pixel files in /sys/class/graphics/fb0.