Problema interessante. Alguém neste fórum postou adicionando insmod vbe
em sua configuração do grub fez o truque para eles.
A documentação da comunidade Ubuntu para o Grub2 (que é a versão do grub que vem com o Ubuntu 11.04) também deve ajudar. O Seção aqui sugere que você pode sondar resoluções disponíveis a partir do prompt do grub pressionando 'c' na tela principal do grub e digitando o comando 'vbeinfo'. Já que o grub é onde você está, você pode querer tentar isso no CD de instalação do Ubuntu.
Você também pode tentar atualizar esse parâmetro fornecido para algo como:
GRUB_GFXMODE=800x600x16
Dessa forma, você também declara uma profundidade de cor. Eu gostaria de pensar que o Grub iria simplesmente padronizar algo, mas talvez não - ou talvez o padrão seja o que está te matando.
Espero que algo aí te ajude.