- Wait: It can take a loooong time to complete backups and indexing of backups so wait a few hours or even a day or so to see if it just sorts itself out.
- Repair Backup:
- Turn off Time Machine in the preferences.
- Mount the Time Machine Backups as follows: In Finder you navigate to your backup disk and then find your machine's actual backup file (your_computer_name.sparsebundle) and double click on it - it will put a new disk in Finder's sidebar: 'Time Machine Backups'.
- Then open up Disk Utility and select the 'Time Machine Backups' disk and click repair.
- Eject the 'Time Machine Backups' disk and re-enable Time Machine in the system prefs.
sudo rm -rf /Volumes/Time\ Machine\ Backups/.Spotlight-V100
Then follow step (4) above. After this your backups may take longer for a day or so whilst Time Machine rebuilds its indexes but it should settle down soon.
mounted (see (2) above). The going to Spotlight Prefs and adding the disk to the 'Privacy' section. Alternatively it can be done on the command line as follows:
sudo mdutil -i off /Volumes/Time\ Machine\ Backups
[Updated: 26oct12: Cleanup and Pondini link]