Time Machine stuck on "Preparing backup" whenever returning from Boot Camp to OS X

I have Windows 7 installed in Boot Camp. Whenever I go into Windows 7 and then go back to OS X Lion, and then run a Time Machine backup, Time Machine is stuck on the "Preparing Backup" stage for a long time (roughly 30 minutes). It usually takes 30 seconds in this stage in most cases.

The reason it's stuck at this stage is probably because it is re-indexing everything again (per this KB article), but the question is, why does it have to re-index everything again after restarting out of Boot Camp? I think this only started happening in the past few weeks, while I've had Boot Camp installed on this computer for a few years now.