I just had this problem too. It happened when I updated from 10.10 to 11.04 so that might be a good place to look for the solution...
What I did was I opened my Grub config in /etc/default/grub (You may need to open this with sudo with the following command:
sudo gedit /etc/default/grub
Then find the line with
Un-comment the last line and change it to a supported resolution for your monitor.
# The resolution used on graphical terminal
# note that you can use only modes which your graphic card supports via VBE
# you can see them in real GRUB with the command `vbeinfo'
(I used 800*600, and pretty much any resolution below 1024*786 should work.)
Then the last thing you need to do is type and it will automatically update your Grub configuration files.