You probably did not delete
the MBR. You probably replaced it with the one that boots Umbutu's loader, and there is something wrong with it.
Boot up a LiveCD.
Now you can mount the drive:
mount /dev/hda1 /mnt/hda1
... and take a look at it.
Let's say that you find that yes, the information is there. All you need to do now is to replace the MBR. It makes a difference now whether you're using Lilo or Grub, as others have already said.
Notice also exactly where and how
it fails when you try to start up. If you see a boot-loader starting at all,
then the MBR is present; the problem's in the boot-loader somewhere. If you see Linux starting at all, the prob might be in Linux.
Yes, you get really good
at reading text that's whizzing by very fast.