I presume that the 'no such partition exists' happens when you (try to) boot from the hard disk: it is telling you that Grub cannot find the place where the rest of the stuff required to boot is. This is normally stored on the same partition as the rest of the Ubuntu system, so if you deleeted that partition, you are definitely going to have problems...
Additionally, if the Ubuntu install was originally Ubuntu 9.10 (Karmic Koala) or 10.04, it will be using the newer version of Grub, Grub2, and I don't think that your sudo update-grub command will work as intended with the newer version.
Can you append to your question what partitions and what operating systems were/ are installed on your computer? My guess is that you need to either make a new partition for /boot (which will probably require a re-install of Grub) or, if appropriate, revert to using Windows' mbr.