was the updates done on columns that are index? you did not mention if you ran update stats after the update.