What does "Reindexing blocks on disk" mean?
0.8x versions of the bitcoin-qt client now use a different database to store the blockchain.  This change was necessary to allow for larger block sizes.

The reindexing process is converting the previous database (which used BerkleyDB) into the new one (Which uses LevelDB).