Is it XP or Vista?
I remember reading somewhere (no idea if this is true or not) that Vista can merge two partitions into one, so what you can try is to rewrite your partition table under OS X, break however much you want off of the OS X partition and then boot into Windows to format that new partition to your preferred FS. Then (if this actually possible) merge these two partitions... maybe with Partition Magic.
To rewrite the partition table you will have to play around in Terminal, so if that concept bothers you, then wipe and reinstall.