I upgraded tonight, and experienced this same error with all the same details/problems in my error message. I double-checked fstab and menu.lst and the UUID's were all correct, so I began experimenting with my server:
and found: a Secondary (simpler) possible solution to the
"Alert! /dev/disk/by-uuid/ ...<your UUID>.... does not exit"
Out of morbid curiosity, and after receiving this error (and attempting DOZENS of so-called "fixes"), I decided to boot back into an older kernel through the GRUB menu (an obvious perk over a fresh install). (You could also attempt this simple solution using a liveCD and mounting your /root partition from a Live Desktop environment)
1) Open a terminal
2) Type "sudo apt-get dist-upgrade"
3) When Ubuntu completes all remaining upgrades, reboot.
For some reason, for Ubuntu-Server Jaunty 9.04 release, there is an upgrade bug. If you simply run "upgrade" all of the necessary changes do not complete. A simple "dist-upgrade" completes the circle and flushes out the inconsistencies in drive UUID's.