I just did this whole process about 3 weeks ago.
First off, you should post (actually, SEARCH) in the Windows on Mac forum. I got some great info there. I also googled a lot.
Anyway, as far as reinstalling the OS- you still have your install discs, right? If you do, then just back up through time machine, then put the OSX install disc and then reinstall the OS. I have an OSX Leopard install disc, plus the Snow Leopard upgrade disc. Had to install OSX Leopard, DL all the updates, THEN install SL and get all the updates (that took a LONG time)
Once I was all updated, I went into Boot Camp Assistant to set up a partition (50gb) and went from there! I tried all the other fixes people mentioned, but none worked for me. I had to reinstall and start from scratch. FWIW, migrating everything from my Time Machine backup, while a lengthy process, went smoothly. All my stuff was still there, dock, wallpaper, everything.