Navigating Time machine is also very slow. In Snow Leopard it was much faster.
You might want to try forcing a deep traversal.
Easiest way I've found is to boot from a Snow Leopard DVD and then restart your Mac. Since you've booted from a different O/S install(the DVD) this tells Time Machine that files on the drive might have changed. Thus, forcing a deep traversal.
My full backups are around 152GB and in Lion it now takes hours to complete.
Lion seems to want to do very large backups even if there are only small changes to my data.
I have figured out by now that I don't have this problem only on the Time Machine volume but also on my system volume alot.
At least once per day my Mac forgets the entire Index for / and has to reindex it - just like it happens all the time on my Time Machine Volume.
I found out that sometimes after waking from sleep the mds daemon is stuck and doesn't work anymore. It seems to get killed and restarted eventually. Once that happens either the Time Machine or the / Index are marked as corrupt and will be completely replaced.
This in take turns 50 Minutes on my Mac and 7 hours on my Time Machine Volume.
I think the whole issue is that mds doesn't reliably 'wake from sleep'.