I'm running Ubuntu 13.04. Yesterday I tried to install updates but there was an error, and it suggested running apt-get -f install which I did.

Now when I try to boot, I get an error "Gave up waiting for root device". The text is almost identical to the text shown in this and this question. However, the "built-in shell" simply doesn't work! Nothing I type shows up on the screen or does anything. I tried adding a rootdelay to grub but it just waits longer and shows the same screen.

Loading the previous kernel works (although there are a few graphics glitches) but as far as I can tell, it should be booting the exact same stuff. The new kernel is 3.8.0-31-generic and the previous working one is 3.8.0-25-generic. Here is my entire /boot/grub/menu.lst file, comments removed:

default     0
timeout     3

title       Ubuntu 13.04, kernel 3.8.0-31-generic
uuid        c690c1e6-beb9-46e7-85c2-145cd07d44ac
kernel      /boot/vmlinuz-3.8.0-31-generic root=UUID=c690c1e6-beb9-46e7-85c2-145cd07d44ac rootdelay=120 ro quiet splash 
initrd      /boot/initrd.img-3.8.0-31-generic
quiet

title       Ubuntu 13.04, kernel 3.8.0-31-generic (recovery mode)
uuid        c690c1e6-beb9-46e7-85c2-145cd07d44ac
kernel      /boot/vmlinuz-3.8.0-31-generic root=UUID=c690c1e6-beb9-46e7-85c2-145cd07d44ac ro  single
initrd      /boot/initrd.img-3.8.0-31-generic

title       Ubuntu 13.04, kernel 3.8.0-25-generic
uuid        c690c1e6-beb9-46e7-85c2-145cd07d44ac
kernel      /boot/vmlinuz-3.8.0-25-generic root=UUID=c690c1e6-beb9-46e7-85c2-145cd07d44ac ro quiet splash 
initrd      /boot/initrd.img-3.8.0-25-generic
quiet

title       Ubuntu 13.04, kernel 3.8.0-25-generic (recovery mode)
uuid        c690c1e6-beb9-46e7-85c2-145cd07d44ac
kernel      /boot/vmlinuz-3.8.0-25-generic root=UUID=c690c1e6-beb9-46e7-85c2-145cd07d44ac ro  single
initrd      /boot/initrd.img-3.8.0-25-generic

title       Ubuntu 13.04, kernel 3.8.0-23-generic
uuid        c690c1e6-beb9-46e7-85c2-145cd07d44ac
kernel      /boot/vmlinuz-3.8.0-23-generic root=UUID=c690c1e6-beb9-46e7-85c2-145cd07d44ac ro quiet splash 
initrd      /boot/initrd.img-3.8.0-23-generic
quiet

title       Ubuntu 13.04, kernel 3.8.0-23-generic (recovery mode)
uuid        c690c1e6-beb9-46e7-85c2-145cd07d44ac
kernel      /boot/vmlinuz-3.8.0-23-generic root=UUID=c690c1e6-beb9-46e7-85c2-145cd07d44ac ro  single
initrd      /boot/initrd.img-3.8.0-23-generic

title       Ubuntu 13.04, memtest86+
uuid        c690c1e6-beb9-46e7-85c2-145cd07d44ac
kernel      /boot/memtest86+.bin
quiet

title       --------------------------------
root

title       Windows Vista
rootnoverify    (hd0,2)
savedefault
makeactive
chainloader +1

As you can see the UUID is the same for all kernels.

Why am I getting this problem, and what can I do to fix it?