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:
- 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.
- Boot the install CD and select Rescue mode under Advanced options.
- 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.
- 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):
- Make sure that the network interface is up (ifup eth0).
- Make sure that
/etc/resolv.confhas at least one nameserver line, otherwise add one. - Install the latest version using
apt-getordpkg.
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 
The method I use is to boot another copy of Grub from somewhere (bootable CD, USB stick, or network boot -- it's easy to boot grub from any of these). Then, from the prompt, something like:
is all you need to install grub onto the disk.
Or, if you'd rather just boot into the system and fix it from there, I use something like:
(press escape)
grub-mkconfig(because I have changed the boot partition). After that, the computer was able to boot successfully.