How long should Lion take to set up Spotlight?
Solution 1:
First off - Spotlight works incrementally as you write any data to the drive. This processing has filters and pattern detectors that extract information from files and store those "nuggets" in a database structure that allows spotlight to find things.
Lion changed the filters, so your old database is now out of date. The entire hard drive has now to pass through the changed filters one time. The first pass could be done in about the same time as the install took if you have nothing on the mac.
It's hard to know what type of files you have - as spotlight will take a lot longer to index a 5 MB text file than it will a 5 MB music file. Using the mac will slow down the updating, so many people turn off spotlight after an upgrade and let it do the entire drive scan over night or when you are away from the Mac so it can just do that one task without slowing you down.
I would say most macs that can run Lion should be done indexing in 12 hours unless there are problems. Those problems usually have messages in the console log (/var/log/system.log) - but it's probably just something you need to wait out.