Well, repairing grub stage1 & stage1.5 is usually easy. I didn't understand cleary what kind of changes you made to your disk partitioning (you added or removed some partitions ?), but reinstalling grub should fix the problem.
The easiest way is, first, to make a grub boot floppy/usb. Then, you boot from it, and you'll get a grub prompt. Then, you enter those simple commands:
- find /boot/grub/stage2
- root (hdX, Y)
- setup (hdZ)
Where X and Y are value you take from the output of the find command. If you don't get any output, well then you have a problem and you'll have to investigate further. In simple setup (i.e. where you have only one drive -- or at least when all your OS are on the same drive), Z will be equal to X, except if you are just weird and installed the bootloader on the data drive...
As for making a grub boot floppy/usb, instructions are here.
Creating a GRUB boot floppy - GNU GRUB Manual 0.97
Instructions are for floppy disk; in the case you want to use a usb stick, replace every occurence of "/dev/fd0" to your usb device (you'll need to find this by yourself, but it should be something similar to "/dev/sdb"). Note that you'll lose all the stuff on your usb stick (and you'll need to repartition it after, which you can do with, at least, tools like gparted). Also, note that you should unmount any filesystem on your usb stick before making it grub bootable.