use um editor (como vim ou nano) e edite seu /boot/grub/menu.lst (você terá privilégios de root). lá você vai encontrar isso:
# FRAMEBUFFER RESOLUTION SETTINGS
# +-------------------------------------------------+
# | 640x480 800x600 1024x768 1280x1024
# ----+--------------------------------------------
# 256 | 0x301=769 0x303=771 0x305=773 0x307=775
# 32K | 0x310=784 0x313=787 0x316=790 0x319=793
# 64K | 0x311=785 0x314=788 0x317=791 0x31A=794
# 16M | 0x312=786 0x315=789 0x318=792 0x31B=795
# +-------------------------------------------------+
que lhe dá as resoluções para o console ser carregado na inicialização ... depois de decidir qual é a certa para você, você deve adicionar mais um parâmetro (também no seu grub) à seguinte linha:
kernel /vmlinuz26 root=/dev/sda1 ro vga=775
(é a parte VGA ... basta digitar o número correto)
editar: ok, esqueça a parte superior, é para o grub1 ... aqui está o que você deve fazer para grub2:
O link no grub.cfg edita o seguinte:
GRUB_GFXMODE=1280x800x32
GRUB_GFXPAYLOAD_LINUX=keep