Hi, I have a similar issue: Ubuntu is installed on /dev/hda10, but when updater updates grub/menu.lst it uses the UUID of /dev/hda9 (where debian unstable) is installed.

Here my fstab, menu.lst and the output of blkid. I hope this will help.

########################
# /etc/fstab: static file system information.
#
# <file system> <mount point>   <type>  <options>       <dump>  <pass>
proc            /proc           proc    defaults        0       0
# /dev/sda10
UUID=dcb27ef8-f2db-48b0-a701-326a33d777bc /               ext3    defaults,errors=remount-ro 0       1
# /dev/sda1
UUID=4664CF3F64CF310B /media/sda1     ntfs    defaults,nls=utf8,umask=007,gid=46 0       1
# /dev/sda5
UUID=0A0CD1B60CD19D4F /media/sda5     ntfs    defaults,nls=utf8,umask=007,gid=46 0       1
# /dev/sda6
UUID=8d360ab6-29ad-4a20-852e-5bce779fb660 /media/sda6     ext3    defaults        0       2
# /dev/sda8
UUID=bbb17398-320e-4920-aa2e-fb1f92a36161 /media/sda8     ext3    defaults        0       2
# /dev/sda9
UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c /media/sda9     ext3    defaults        0       2
# /dev/sda7
UUID=9f28e9d7-5017-45bb-a3a2-77fd4eafc4b2 none            swap    sw              0       0
/dev/scd0       /media/cdrom0   udf,iso9660 user,noauto     0       0
/dev/scd1       /media/cdrom1   udf,iso9660 user,noauto     0       0
/dev/fd0        /media/floppy0  auto    rw,user,noauto  0       0


###########################
###########################
# menu.lst - See: grub(8), info grub, update-grub(8)
#            grub-install(8), grub-floppy(8),
#            grub-md5-crypt, /usr/share/doc/grub
#            and /usr/share/doc/grub-doc/.

## default num
# Set the default entry to the entry number NUM. Numbering starts from 0, and
# the entry number 0 is the default if the command is not used.
#
# You can specify 'saved' instead of a number. In this case, the default entry
# is the entry saved with the command 'savedefault'.
default         saved

## timeout sec
# Set a timeout, in SEC seconds, before automatically booting the default entry
# (normally the first entry defined).
timeout         5

# Pretty colours
color cyan/blue white/blue

## password ['--md5'] passwd
# If used in the first section of a menu file, disable all interactive editing
# control (menu entry editor and command-line)  and entries protected by the
# command 'lock'
# e.g. password topsecret
#      password --md5 $1$gLhU0/$aW78kHK1QfV3P2b2znUoe/
# password topsecret

#
# examples
#
# title         Windows 95/98/NT/2000
# root          (hd0,0)
# makeactive
# chainloader   +1
#
# title         Linux
# root          (hd0,1)
# kernel        /vmlinuz root=/dev/hda2 ro
#

#
# Put static boot stanzas before and/or after AUTOMAGIC KERNEL LIST

### BEGIN AUTOMAGIC KERNELS LIST
## lines between the AUTOMAGIC KERNELS LIST markers will be modified
## by the debian update-grub script except for the default options below

## DO NOT UNCOMMENT THEM, Just edit them to your needs

## ## Start Default Options ##
## default kernel options
## default kernel options for automagic boot options
## If you want special options for specific kernels use kopt_x_y_z
## where x.y.z is kernel version. Minor versions can be omitted.
## e.g. kopt=root=/dev/hda1 ro
##      kopt_2_6_8=root=/dev/hdc1 ro
##      kopt_2_6_8_2_686=root=/dev/hdc2 ro
# kopt=root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro

## Setup crashdump menu entries
## e.g. crashdump=1
# crashdump=0

## default grub root device
## e.g. groot=(hd0,0)
# groot=(hd0,9)

## should update-grub create alternative automagic boot options
## e.g. alternative=true
##      alternative=false
# alternative=true

## should update-grub lock alternative automagic boot options
## e.g. lockalternative=true
##      lockalternative=false
# lockalternative=false

## additional options to use with the default boot option, but not with the
## alternatives
## e.g. defoptions=vga=791 resume=/dev/hda5
# defoptions=

## should update-grub lock old automagic boot options
## e.g. lockold=false
##      lockold=true
# lockold=false

## Xen hypervisor options to use with the default Xen boot option
# xenhopt=

## Xen Linux kernel options to use with the default Xen boot option
# xenkopt=console=tty0

## altoption boot targets option
## multiple altoptions lines are allowed
## e.g. altoptions=(extra menu suffix) extra boot options
##      altoptions=(recovery) single
# altoptions=(recovery mode) single

## controls how many kernels should be put into the menu.lst
## only counts the first occurence of a kernel, not the
## alternative kernel options
## e.g. howmany=all
##      howmany=7
# howmany=all

## should update-grub create memtest86 boot option
## e.g. memtest86=true
##      memtest86=false
# memtest86=true

## should update-grub adjust the value of the default booted system
## can be true or false
# updatedefaultentry=false

## ## End Default Options ##

title           Xen 3.0-i386-pae / Ubuntu, kernel 2.6.19-4-generic
root            (hd0,9)
kernel          /boot/xen-3.0-i386-pae.gz
module          /boot/vmlinuz-2.6.19-4-generic root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro console=tty0
module          /boot/initrd.img-2.6.19-4-generic
quiet
savedefault

title           Xen 3.0-i386 / Ubuntu, kernel 2.6.19-4-generic
root            (hd0,9)
kernel          /boot/xen-3.0-i386.gz
module          /boot/vmlinuz-2.6.19-4-generic root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro console=tty0
module          /boot/initrd.img-2.6.19-4-generic
quiet
savedefault

title           Xen 3.0-i386-pae / Ubuntu, kernel 2.6.19-4-server
root            (hd0,9)
kernel          /boot/xen-3.0-i386-pae.gz
module          /boot/vmlinuz-2.6.19-4-server root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro console=tty0
quiet
savedefault

title           Xen 3.0-i386 / Ubuntu, kernel 2.6.19-4-server
root            (hd0,9)
kernel          /boot/xen-3.0-i386.gz
module          /boot/vmlinuz-2.6.19-4-server root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro console=tty0
quiet
savedefault

title           Ubuntu, kernel 2.6.20-13-lowlatency
root            (hd0,9)
kernel          /boot/vmlinuz-2.6.20-13-lowlatency root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro
initrd          /boot/initrd.img-2.6.20-13-lowlatency
quiet
savedefault

title           Ubuntu, kernel 2.6.20-13-lowlatency (recovery mode)
root            (hd0,9)
kernel          /boot/vmlinuz-2.6.20-13-lowlatency root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro single
initrd          /boot/initrd.img-2.6.20-13-lowlatency

title           Ubuntu, kernel 2.6.20-13-generic
root            (hd0,9)
kernel          /boot/vmlinuz-2.6.20-13-generic root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro
initrd          /boot/initrd.img-2.6.20-13-generic
quiet
savedefault

title           Ubuntu, kernel 2.6.20-13-generic (recovery mode)
root            (hd0,9)
kernel          /boot/vmlinuz-2.6.20-13-generic root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro single
initrd          /boot/initrd.img-2.6.20-13-generic

title           Ubuntu, kernel 2.6.19-4-server
root            (hd0,9)
kernel          /boot/vmlinuz-2.6.19-4-server root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro
quiet
savedefault

title           Ubuntu, kernel 2.6.19-4-server (recovery mode)
root            (hd0,9)
kernel          /boot/vmlinuz-2.6.19-4-server root=UUID=5e0b2840-d37e-4e69-842c-3be3bd16819c ro single

title           Ubuntu, memtest86+
root            (hd0,9)
kernel          /boot/memtest86+.bin
quiet

### END DEBIAN AUTOMAGIC KERNELS LIST


######################
###################### blkid
/dev/hda1: TYPE="ntfs"
/dev/hda5: TYPE="ntfs"
/dev/hda6: UUID="8d360ab6-29ad-4a20-852e-5bce779fb660" SEC_TYPE="ext2" TYPE="ext3"
/dev/hda7: TYPE="swap" UUID="9f28e9d7-5017-45bb-a3a2-77fd4eafc4b2"
/dev/hda8: LABEL="/1" UUID="bbb17398-320e-4920-aa2e-fb1f92a36161" SEC_TYPE="ext2" TYPE="ext3"
/dev/hda9: LABEL="/" UUID="5e0b2840-d37e-4e69-842c-3be3bd16819c" SEC_TYPE="ext2" TYPE="ext3"
/dev/hda10: UUID="dcb27ef8-f2db-48b0-a701-326a33d777bc" SEC_TYPE="ext2" TYPE="ext3"