Perhaps the configuration of grub is not correct? Don't know with Ubuntu, but with Gentoo there is a file in /boot/grub/ called "grub.conf" (or perhaps "menu.1st") which contains the configuration of the partitions and where to find the root partition. E.g.:
title=Gentoo Linux 2.6.24-gentoo-r4
kernel /boot/kernel-2.6.24-gentoo-r4 root=/dev/sda3 vga=0x317 console=tty1
In your case perhaps the "root (hd0,0)" and/or the "root=/dev/sda3" might be wrong? Well, not exactly "sda3", but whatever is mentioned there in your config?