I know that it is a bit late for resolving the problem, since you got the system working, but I provide two different solutions.
Removing a partition does not remove the data. Think of the disk as a contiguous space of sectors (long 512, 4096 bytes or so). The information about disk partitioning is stored (for MBR a.k.a. DOS partition table) in the first sector or (for GPT) somewhere at the start and the end of the disk. The rest of disk is left for the partitions. Removing a partition only deletes the record about it in the are where the information about it is stored but not the actual partition data. The partition data will get overwritten only if you create another partition in the same area (or part of it) and write to it. So, when you create the same partition again, everything will work again. Just make sure that it has the same UUID (or change the UUID in GRUB config and fstab), type, position etc.
Use the installation disk for repair. Debian installation CD, and if I remember correctly, also the Ubuntu installation disk has in its text-mode variant a tool exactly for these problems. It can reinstall GRUB or LILO or add it to moved installation. It can also reinstall core system packages etc.