Your partitions are renumbered now. (I think) You just have to figure out the new numbers, then it should work, unless there is something else funky going on. Can you boot a live cd and use gparted or fdisk to figure out the correct partition numbers now, then edit menu.list to the correct values. Let us know how it goes.
You could also try this, it has a funky text menu system, but it does have a pretty cool wizard that goes in and fixes grub for you. At least, it did, I haven't had to use it in a long time.
P.S. Looks like I misunderstood your situation a little. I think you can use supergrub disk to rebuild grub on your MBR, then everything should start up just fine. What distro did you have in the deleted partition before ?