i have not confirmed it yet (still awaiting access to production :angry:) but i am guessing that the issue may be related to the indexes being on typically integer data...
I don't think there is any reindexing going on first, since the update stats script checks first to ensure it only runs where last update > 24 hours ago....