Time Machine stuck on "Preparing backup" whenever returning from Boot Camp to OS X
Okay so I figured this out a while ago, but I'll post it here too. The problem was I was using MacDrive, which allows me to read and write to Mac partitions while in Windows (using Boot Camp).

MacDrive sometimes modified files on the Mac partitions even if I didn't open them; I think it sometimes perform optimization actions to speed up the reading of Mac partitions.

This means that when I return to Mac OS X, Time Machine notices that a Mac partition was changed while outside of OS X, so it reindexes everything to be sure it doesn't miss anything.