I would up-vote this, but apparently I don't have enough rep on SuperUser. I'm glad I finally found an answer to this after days of fighting clones that worked but wouldn't boot. I think it all relates to UEFI and some kind of "secure booting" mechanism or something.
I'm working off-line, so apt-get wasn't an option. What I did was put Ubuntu Desktop on a USB stick, add the
grub-efi-amd64 packages to the root of the USB stick (grub-efi_1.99~rc1-13ubuntu3_amd64.deb and grub-efi-amd64_1.99~rc1-13ubuntu3_amd64.deb for Ubuntu 11.04 - change as appropriate for distro and architecture), and put the following in a script on the USB stick as well:
sudo mount /dev/sda2 /mnt
sudo mount /dev/sda1 /mnt/boot/efi
sudo cp $dir/grub-efi*.deb /mnt/tmp
for i in /dev /dev/pts /proc /sys; do sudo mount -B $i /mnt$i; done
sudo chroot /mnt /bin/sh -c "dpkg -i /tmp/grub-efi*.deb"
sudo shutdown -r now
Boot up the Live USB stick, open a terminal, run the command, and the job is a good 'un! The only occasional problem is that UEFI sometimes got moved down the boot priority order below the HDD, at which point you need to go into the BIOS and change the boot order to stop it trying (and failing) on
You can also use
dpkg-reconfigure instead of
dpkg -i, but that asks a couple of boot loader questions.
 I also don't have enough rep to comment, so what I thought was a comment on a reply turns out to be a reply.