When you installed Ubuntu, it wrote part of the grub bootloader to the MBR (master boot record) of the hard drive. When you deleted the Ubuntu partition, the part of grub in the MBR was not removed. It is still there.
Now, your other OS does not have it's own bootloader in the MBR, and grub cannot find the rest of grub (it has been deleted). If your other OS is windows, you need to boot a windows install disk and run fixmbr to restore the MBR for windows. If you have an old windows 98 install disk, you can run fix mbr to repair the MBR for windows.