I've had problems many times with the "reading database" step in deb package based systems getting really slow. Today it took over 1,5 minute on a quad core machine with 4 gig ram, which is simply over the top for me.
Within 5 minutes of searching I found this:
http://antti-juhani.kaijanaho.fi/newblog/archives/521
So a total of 7 minutes later, it takes me less than 2 seconds to install small packages again. I should've found this earlier :-).
