Boot into the live Ubuntu cd.
When you get to the desktop open a terminal and enter.
This will get you a "grub>" prompt (i.e. the grub shell). At grub>. enter these commands
Whatever was returned for the find command use it in the next step (you are still at grub>.
grub >find /boot/grub/stage1
Again use the value from the find command i.e. if find returned (hd0,1) then you would enter root (hd0,1)
Next enter the command to install grub to the mbr
Then exit the grub shell
I just think the root was not set properly.
The hd0 is the proper device though....