This problem appeared when I upgraded to Ubuntu 9.10 from 9.04. The UUID of my root partition disappeared: it does not show up in /dev/disk/by-uuid and it is not reported by "blkid -c /dev/null /dev/sda1", but the setting in /etc/fstab still mentioned the old UUID. So I tried
tune2fs /dev/sda1 -U <old-uuid>
After this "tune2fs -l /dev/sda1" displays, among other things
Filesystem UUID: b11593cd-267d-458b-8fc8-4b2ca6b2fdcc
which is fine. However, the UUID still doesn't appear in /dev/disk/by-uuid, is not reported by "blkid -c /dev/null /dev/sda1" (which prints nothing!), and can't be used for mounting.
In general, "tune2fs -l" always prints the latest thing set (or cleared) with "tune2fs -U", but other tools, such as 'mount' and 'blkid' don't seem to see the change.
Probably unrelated, I mention that the swap partition kept its old UUID and there's no problem with it.
tune2fs 1.41.9 (22-Aug-2009)
rg@rg-ucd:temp$ blkid -v
blkid from util-linux-ng 2.16 (libblkid 2.16.0, 10-Feb-2009)