Change in GRUB menu.lst does not take effect

I'm working on a system (Ubuntu 9.04) which has RAID 10 on 6x1TB disks. Over this there is a LVM setup. I needed to install a new kernel on this system and everything went smoothly. I updated the /boot/grub/menu.lst file to boot with the new kernel.

However, while booting, the newly installed kernel is not seen in the list and the system still boots with the old kernel.

I re-checked the installation logs of the new kernel and there were no errors. I ran 'update-grub' and it selects all the kernels available in /boot. However, when I run 'grub-install' it throws the following error:
/dev/mapper/vg-root does not have any corresponding BIOS drive.

I tried to do this from the grub command line:

grub> find /grub/stage1
find /grub/stage1
(hd0,0)
grub> find /grub/stage2
find /grub/stage2
(hd0,0)
grub> find /grub/menu.lst
find /grub/menu.lst
(hd0,0)
grub> root (hd0,0)
root (hd0,0)
grub> setup (hd0)
setup (hd0)
Checking if "/boot/grub/stage1" exists... no
Checking if "/grub/stage1" exists... yes
Checking if "/grub/stage2" exists... yes
Checking if "/grub/e2fs_stage1_5" exists... yes
Running "embed /grub/e2fs_stage1_5 (hd0)"... failed (this is not fatal)
Running "embed /grub/e2fs_stage1_5 (hd0,0)"... failed (this is not fatal)
Running "install /grub/stage1 (hd0) /grub/stage2 p /grub/menu.lst "... succeeded
Done.
grub> quit


However, it still doesn't work. The groot in menu.lst is shown as "groot=(hd0,0)" (used by update-grub) and the /boot is on LVM:

df /boot
Filesystem 1K-blocks Used Available Use% Mounted on
/dev/mapper/vg-root 19223252 1140336 17106432 7% /


.. and the device.map file looks like:

(fd0) /dev/fd0
(hd0) /dev/sda


I'm running out of ideas. Any help on this will be highly appreciated.

Thanks,
- NNS