that Clinton was following 12 years of Republican administration, so it only made sense that he would want to clean house right after he took office, to purge the leftovers from previous administrations.

Now, if he had waited several years, and then said "I'm going to selectively remove a handful of AGs", well, then you might have a point.