So, it's definitely true that /dev/sda is not a reliable way to identify
any given disk. We moved to UUIDs for mounting filesystems from
partitions precisely because such names are unreliable. The kernel
believes itself entitled to enumerate SATA (and many other) devices in
any order it pleases - indeed, it has no choice on some SCSI systems, or
given that the enumeration namespace is shared with USB, etc. - and it
will frequently not use the order you might expect. Applications are
supposed to cope in other ways. This has been an ongoing headache in
various places for years - it's not unique to GRUB 2 in Karmic by any
stretch of the imagination, though you might have been lucky enough to
have escaped its deathly touch until now.

That said, UUIDs are a property of filesystems, not of disks. The only
reliable and suitable way I can think of to identify disks is to use the
names under /dev/disk/by-id/ rather than the traditional Linux device
names; those essentially identify the general type (e.g. SATA), the
manufacturer's name, and a unique serial number for the disk, packed
into a device name format. In short they uniquely identify a given
physical disk, or a numbered partition on a given physical disk, but not
any kind of logical construct on that disk (so they aren't suitable for
filesystem mounting where you care much more about the contents). See
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=509378#24 for a related
discussion.

Felix, if you're reading, what do you think of the following approach?

 * If the directory /dev/disk/by-id exists (it should more or less
   always exist if you're using udev), then always store device names
   under /dev/disk/by-id/ in grub-pc/install_devices. Map them back to
   the traditional names as found in device.map before using them.

 * It's probably not suitable to actually display /dev/disk/by-id/ names
   to users, e.g. in the list of choices for that template. Instead,
   display either the traditional Linux device name, or (preferably)
   some kind of "friendly" name, including such things as the size of
   the disk. See d-i's partitioner for a partial model here.

 * grub-installer should do this translation too.

 * On upgrade to the first version implementing this, if /dev/disk/by-id
   exists and grub-pc/install_devices does not already contain suitable
   names (the latter check may be unnecessary, as more or less nobody's
   will), *ask again*, possibly with different text. The reason for this
   is that their stored list of install devices might well be incorrect,
   and we want to make sure that we get it accurate as soon as we can
   store it accurately, and then store it accurately henceforth.

 * If ever it is discovered that the stored list of install devices
   includes a disk that no longer exists, ask the question again. This
   is probably because a disk was swapped out for a different one, and
   we almost certainly need new information on the state of the system.
   In this case especially, we may need to regenerate device.map; in
   general I think grub-setup falls over if it's asked to install to a
   disk not listed in device.map, although for our purposes it doesn't
   matter much if device.map is accurate since for everything important
   we supersede the GRUB device names with UUIDs. The device just needs
   to be there at all.

This will probably involve some moderately complicated use of debconf.
I'm willing to write the code if we're broadly agreed. We're getting far
too many reports indicating this general kind of problem, and I want to
hit it as hard as possible with the most appropriately-shaped hammer I
can find before we release Ubuntu 9.10.