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.
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.
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).
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.
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.
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.