Following this metaphor though, the population will be *glad* to get rid of their old rulers. I would say that a loyalty based TO of a region that's been ruled through fear should proceed more quickly BUT that when it succeeds, the starting loyalty to the new realm will be tenuous at best. You will have to work very hard to keep their trust or they will quickly become rebellious.
The difficultly encountered in several wars with Heart and Mind campaigns to win over oppressed people would suggest this is not the case. When a population has been subject to severe oppression, they do not give their trust to a new group easily, they live in constant fear, they doubt the sincerity of their new masters, they worry that it is just the beginning of some new form of oppression. You know you are sincere and truly wish to earn their loyalty, they are just waiting for the whip to return.
They also have a hard time accepting that they are truly free of their Old masters, or that their old masters won't come back.
