While reading about this problem, I thought about a possible reason why you can't boot in Vista:
Maybe the BCD store (the Vista's boot sector) was stored on the recovery partition. That's the folder "Boot" on the C: drive. And when you formatted that recovery partition (which I suppose had a "boot" flag), the flag was removed.
A simple solution is to put the Vista install DVD in the drive, boot from it, and choose repair, there you'll find an option for fixing the boot process. If you do this, you won't be able to boot into Mint unless you install the BCDEdit application on Vista and from there add the Mint partition in the boot list, or if you use a Live CD of Mint, use gparted and set the flag of "boot" to the partition where Mint is installed (but then, you must edit the grub's menu.lst and manually add entries for Vista).
Or, using gparted, highlight the partition where you installed Vista, right-click it, choose "Manage Flags" and make sure the "boot" flag is checked. If you do this, Vista will boot the next time you start the PC, not Mint.
Reinstalling Mint won't solve the problem. It has nothing to do with it.
Just in case, to be sure the partitions are OK, check the partition where Vista is located (not using gparted, but using the install DVD and choosing the recovery option, using the Command Line and "chkdsk").
Hope it helps.