Hey Neresis! I actually did basically the same exact thing a few weeks ago (last time I trust Microsoft with important things). A good first step is to boot using a LiveCD, then open up a terminal and run testdisk (I never actually used it from the Live CD so you may need to dl it first...).
Once you've got it running, (and have created a backup), run a scan. It may take a bit, and may not find the partitions you had in place. When it is done, and hasn't yet found everything, run a "Deeper Scan." This takes a while, but will find just about every partition you ever had.
After it is done, you then have the option of viewing, and most importantly, backing up all the files you once thought were unreachable. I would recommend doing this before proceeding.
At this point, you can select your old partition structure, and save it to the MBR, and quit testdisk.
Where * is the number of your harddrive, and ** is the boot partition of your Ubuntu installation.
> root (hd*,**)
> setup (hd*)
At this point, you should be able to reboot into Ubuntu. However, this is where I gave up, as I just got the important stuff (my data) off my poor, abused partitions, so I just wiped my hdd, and reinstalled everything fresh.
Best of luck, and let me know if you need any more help.