After update, get "error: file not found." followed by "grub rescue> _"

Use Boot Repair to fix your bootloader.

1. Boot Ubuntu from a LiveCD or Live USB
2. Connect to the internet

3. Open a terminal, and add the Boot Repair PPA

   sudo add-apt-repository ppa:yannubuntu/boot-repair && sudo apt-get update

4. Install Boot Repair

   sudo apt-get install -y boot-repair && boot-repair

5. Launch and use, see https://help.ubuntu.com/community/Boot-Repair#Using_Boot-Repair for more details

1. Type ls to get a list of partitions
2. Enter set prefix=(hd0,msdos6)/boot/grub [you will almost certainly have to enter a different drive/partition in the brackets, you may just have to try all of those listed by ls until you find the one that works.
3. Type insmod normal
4. Type normal and you will get your boot prompt back!

See also: The helpful place where I found this. I doubt this will work for everyone encountering this error, but I've put it here in the hope it helps someone.

Once you've loaded Ubuntu, run sudo grub-install /dev/sda and sudo update-grub as soon as possible. This means you won't have to do that tedious process above every time you boot your machine.

I had the exact same issue - normal.mod not found, ls of the boot partition would produce a blank line. After a week of troubleshooting to get the system to boot properly here are the steps I went through.

1. Got a copy of SuperGrub and created a boot cd. I could now get logged back on to my system. Got a copy of BootRepair and had not luck getting the system to boot directly from the hard disk and had to keep using the CD. BootRepair did act a little strange since the Grub location and Grub options were grayed out. It did report a successful install.

2. Hard drive was originally set up:
   sda1 ext4 root with boot
sda2 linux swap
sda3 ext4 used as a spare drive (holds VMs for Virtual box).

3. Used a copy of Ubuntu 10.10 live cd. Ran gparted to shrink the sda1 partition and created sda4 ext4 boot partition at the front of the drive and set mount point to /boot after deleting the boot directory from /. BootRepair now has options available. Installed on boot partition and can now boot from hard drive.

4. Being curious I decided to investigate further. The boot repair log had a peculiar entry for my sda1 ext4 partition, it was reported as DOS and had a short 8 character UUID instead of the UUID reported by blkid. grub-probe reported the file system as vfat.

5. After many other trials I cleared the first 440 bytes of sda1 partition record. Grub-probe now reports file system as ext2. Ran update-grub and the correct UUID for the sda1 partition appears.

The issue seems to be two-fold:
1. It seem to affect installations where the partition record has references to msdos.
2. grub-probe does not try to resolve mismatch issues between fs type and contents in the partition record.