...for those backing up over WiFi to a Time Capsule. If you hae a different configuration, these instructions will not help.
Lion seems to be much more picky about its Spotlight indexes than previous versions of MacOS X. Lion is much quicker to flag a drive's Spotlight index as bad and require the drive to be reindexed. I have had a couple of situations where I've locked up my machine (I'm a developer and do some unusual things). I've had to manually power off the machine to regain control. When that happens, Spotlight wants to reindex all of my drives. For the internal drive, that is not a big deal - an hour or two of a pokey Lion and then it is done. For Time Machine, it is a serious issue.
Spotlight reindexing is a normal part of Time Machine. After Time Machine runs for a couple of minutes, you should see mds processes kick off for a little bit. Then your Time Machine should unmount itself and life will go back to normal. If, however, you have had to do something drastic like power-cycle your machine, Spotlight in Lion may want to rebuild the index for your entire Time Machine backup. If you are connected over WiFi, this process will probably take longer than the evolutionary cycle of the current species of human beings.
What you have to do if this happens is switch from WiFi to Ethernet. The easiest solution is just to plug in Ethernet and reboot. This will reset all of your network connections and will prefer the faster Ethernet over WiFi. Then, turn off automatic Time Machine backups temporarily. Next, open a Finder window on your desktop and enter Time Machine. When it comes up and you see your history, just exit. This is to manually mount your Time Machine drive. Spotlight will detect that it is not happy with the index and will then re-build it. Afer the reindex is complete in a hour or so, manually eject your Time Machine drive, unplug Ethernet, and you should be back to normal.
This happened to me again yesterday. I have a 2007 MacBook and with the twin Pratt & Whitney turbofans, I can always tell when the CPU is working because my neighbors complain they can't hear the airport noise anymore. I had downloaded Xcode 4.2 (a 3.5 GB download) overnight and the machine was locked up in the morning. Being an impatient fellow, I just held the power button. When it came back, it seemed normal. Then Time Machine kicked in and didn't seem to want to turn off. I had downloaded Xcode 4.2 and thought that it was just that big 3.5 GB file that was causing the problem. I let it go this time. I happened to wake up a 2 or 3 am and could hear the machine from the other room - not good. I went in, the CPU was working so hard I could barely get control again. I didn't want to bother so I just closed the lid and waited until it went to sleep. This morning, I switched from WiFi to Ethernet, rebooted, and in less than an hour things are now back to normal.
The moral of my story? Don't force a shutdown of your machine if you can avoid it. If you can't avoid it, pay attention to Activity Monitor and Console. If you see processes kernel_task and mds working hard, run Console.app and search for "backup". If you see a message like:
2011-08-03 8:04:38.600 PM mds: (Normal) DiskStore: Rebuilding index for /Volumes/Time Machine Backups/Backups.backupdb
it means your index is being rebuilt.
If you see:
2011-08-04 1:15:32.487 AM com.apple.backupd: Backup completed successfully.
2011-08-04 1:16:12.566 AM com.apple.backupd: Waiting for Spotlight to finish indexing /Volumes/Time Machine Backups/Backups.backupdb
2011-08-04 1:26:12.723 AM com.apple.backupd: Waiting for Spotlight to finish indexing /Volumes/Time Machine Backups/Backups.backupdb
2011-08-04 1:36:12.871 AM com.apple.backupd: Waiting for Spotlight to finish indexing /Volumes/Time Machine Backups/Backups.backupdb
2011-08-04 1:46:13.028 AM com.apple.backupd: Waiting for Spotlight to finish indexing /Volumes/Time Machine Backups/Backups.backupdb
2011-08-04 1:56:13.179 AM com.apple.backupd: Waiting for Spotlight to finish indexing /Volumes/Time Machine Backups/Backups.backupdb
It means there was a backup at 1:15 AM (with zero changed files) and the reindex was still not done an hour later - bad sign.
If you have a MacBook Air without Ethernet - bummer. Maybe get yourself a faster Time Capsule. I have a 2007 MacBook and a 2nd hand, 1st generation Time Capsule, so my WiFi isn't as fast as it would be with current products.
If you aren't using a Time Capsule but are having other slowness/CPU/fan issues in Lion - sorry. This is one of my few complaints in Lion. I'm also not happy with Preview or the loss of "Save As". Otherwise, I'm a happy camper.
A key part of this is paying attention to Activity Monitor and Console. This will be more important for those of you with new machine that don't have the handy audible CPU alert of the old MacBooks.
Hope this helps a few people. If it doesn't help your particular problem, sorry.