Grub update renders system unbootable

[Lev Kandel]

Did a clean install of Natty on a new 120G SSD. No dual boot, no custom partitions -- I let the installer partition it as it wants. The system installed and worked fine until the last grub update, at which point it became unbootable ("invalid arch independent ELF magic" + rescue shell). grub-install complains, "This GPT partition label has no BIOS Boot Partition; embedding won't be possible!"

After unsuccessfully trying to fix the bootloader, I reinstalled the OS from scratch, again with no custom partitions. Again, the freshly installed system boots fine, but after the first automatic upgrade becomes unbootable.

Attaching the output of boot_info_script.sh.

ProblemType: Bug
DistroRelease: Ubuntu 11.04
Package: grub-pc 1.99~rc1-13ubuntu3
ProcVersionSignature: Ubuntu 2.6.38-10.46-generic 2.6.38.7
Uname: Linux 2.6.38-10-generic x86_64
Architecture: amd64
Date: Thu Jul 21 22:26:56 2011
InstallationMedia: Ubuntu 11.04 "Natty Narwhal" - Release amd64 (20110427.1)
ProcEnviron:
 LANGUAGE=en_US:en
 LANG=en_US.UTF-8
 SHELL=/bin/bash
SourcePackage: grub2
UpgradeStatus: Upgraded to natty on 2011-07-14 (8 days ago)

[Lev Kandel (y5b2rqi02)]

This is also in the attached file, but to make it more obvious, here is the partition table created by the installer:

$ sudo parted /dev/sda print
Model: ATA Corsair CSSD-F12 (scsi)
Disk /dev/sda: 120GB
Sector size (logical/physical): 512B/512B
Partition Table: gpt

Number Start End Size File system Name Flags
 1 17.4kB 20.0MB 20.0MB fat16 boot
 2 20.0MB 111GB 111GB ext4
 3 111GB 120GB 8569MB linux-swap(v1)

[Lev Kandel (y5b2rqi02)]

I now understand what happened. The installer creates (by default) an EFI install, with grub-efi-amd64. The automatic update replaces grub-efi with grub-pc, and the latter doesn't work. I manually reinstalled grub-efi and everything works now.
But something is clearly wrong: an automatic update shouldn't be breaking a clean install. So, what went wrong here? Is it a bug in the installer? in grub? in apt? Should I have done anything differently during installation?