Fixing an unbootable computer after a failed grub installation can be a bit tricky. Here's what I ended up doing.

First of all, boot the machine up and get access to the root partition:

  1. Get a Debian installation CD for the same architecture (i.e. don't use an i386 CD if your root partition is amd64). The distro version doesn't matter too much: a lenny CD will boot squeeze/sid just fine.
  2. Boot the install CD and select Rescue mode under Advanced options.
  3. Answer the language, keyboard and network questions any way you want and provide the decryption passphrases for any of the encrypted partitions you need to mount.
  4. When prompted, request a shell on the root partition.

If you need to upgrade the version of the grub package (for example if this problem was caused by a bug which is now fixed):

  1. Make sure that the network interface is up (ifup eth0).
  2. Make sure that /etc/resolv.conf has at least one nameserver line, otherwise add one.
  3. Install the latest version using apt-get or dpkg.

Now that you have the right grub version, run the following (with the right device name for your machine):

grub-mkdevicemap  
grub-install /dev/hda  
update-grub

Finally, reboot and cross your fingers :)