How do I safely change grub2 screen resolution?

To do this safely requires two steps.

Step 1: find the preferred mode

Reboot and press and hold Shift to display your grub. Press C to enter console mode. Then type (for Ubuntu versions before 18.04):

$ vbeinfo

For Ubuntu 18.04 and later:

$ videoinfo

This will display various stuff how grub recognizes your display. At the bottom is "preferred mode" - in your case it should say 1280x800. Note down the value.

Note: sometimes, some buggy video cards incorrectly give Grub the wrong preferred resolution - if the preferred mode is much higher than you were expecting, then select the nearest mode in the list displayed that you were expecting.

Press Esc to return to grub and press Enter to boot.

Step 2: Setting the resolution in grub

Reach for your terminal and type

$ sudo nano /etc/default/grub

find the line

#GRUB_GFXMODE=640x480

remove the # and change 640x480 with the preferred mode you wrote down. E.g.:

GRUB_GFXMODE=1280x800

save, then type

$ sudo update-grub

Note: the preferred mode has to be among those listed by vbeinfo. For example, if your preferred mode is 1920x1080 (a common 16x9 aspect ratio setting), your preferred mode is NOT supported by vbeinfo and may not work correctly. In fact, there do not seem to be any 16x9 modes supported by vbeinfo, as of Ubuntu 13.04. In that case you could try falling back to something common like 640x480, which, it seems most monitors support and vbeinfo supports. Also, not all the modes supported by vbeinfo are necessarily supported by your monitor and you may have to experiment.

I'm using Ubuntu 16.04 and things are a little different in the packaged version of Grub for me.

The vbeinfo command does not exist.

1. Turn on
2. At the grub menu press c to get the grub comand line
3. Type videoinfo
   This lists all the modes - it is the <width>x<height> you need to make note of.
4. Optionally, there is a videotest command which you can use to test a given resolution, e.g. videotest 1280x1024. However, while this test worked for me, I could not then get back to the grub menu! So that's not quite as useful (unless anyone can explain how to escape the test.)
5. Boot up fully and edit (sudo) /etc/default/grub but the line you're looking for is now called GRUB_GFXMODE. So un-comment and set that to your desired mode.
6. Run update-grub and reboot.

I am running 14.04LTS on an ASUS M51AC with an Nvidia 625GT OEM. I found that in addition to the accepted answer, I needed to also add the line:

GRUB_GFXPAYLOAD="keep"

to /etc/default/grub.