Comment 8 for bug 913615

Oh, one more thing, so obvious it's easy to forget: was the system actually otherwise idle when you noticed the slowness? After a distro install/upgrade, there can be any number of other io-intensive things like prelink, mlocate and man-db cronjobs running which will severely slow down other io-intensive operations such as --rebuilddb.

Robert, if you still have the full original "slow" db (all of it, not just the Packages file) backup somewhere, can you try reproducing it with that, after ensuring the system is really idle? Also the timings for separate --initdb and --rebuilddb as shown in comment #6 might be interesting.