Extreme order can mean a lot of paperwork, but it would also mean extreme efficiency.
It can do. Certainly, that is the goal of order. Efficiency is, however, not necessarily the inevitable outcome.
In the days of the Soviet Union, a highly ordered society, there was a factory that made doors. It had a quota to meet. It had to make so many tons of doors every year. Inefficiency elsewhere meant that there weren't always enough orders for doors. To meet its quota, it ended up making absurdly massive doors. Had its quota been expressed as a number of doors, it would have ended up with lots of doors it could not ship. But its quota was tonnage and so ridiculously massive doors became the order of the day.
On a different note, don't forget the terrible price that can come from trying to maintain a given idea of order. There are states and cultures that provide incentives to encourage their populations to have no more than a certain number of children per family or to maintain a certain ratio of the sexes. Given a couple of decades, you can end up with millions of people who do not officially exist or - even worse - who should exist but don't.
Of course, the OP is talking about sudden change, so these longer term potential consequences are just that - something to be wary of, to be feared, perhaps. And long term consequences often go unseen in the near term.
This change might well make people wonder why it has happened. It sure makes me curious. Maybe the new order is modelling itself on something that exists elsewhere. If this is the case, it is possible that some of the populace are thinking about what they know of that other place. They may fear or welcome the change, depending on their knowledge of this example.
Is there a protest movement? If there is, does it dare show its face? Do the agents of the new order tolerate discussion or do they entrap those they suspect of being a threat do it?
One thing seems certain. Radical change does not manifest overnight, unless it comes from outside or it came from within but then could have been seen gaining momentum. If it is the case that the PCs, without being able to account for it, suddenly find themselves somewhere that seems alien when it shouldn't, alarm bells should start ringing.
I can't help thinking that if I, as a player, came upon this scenario, my PC would be deeply suspicious of it. How cool then would it be for me to discover, eventually, that the forces behind the change were forces of good?