Were you able to resolve your issue?
Do you recall if you had Allow user locale enabled, so your users can choose their own language interface via their preferences? I believe if that is disabled, everyone will be forced to use the default locale you specified in the Default locale setting.
It occurs to me that the Default locale setting should maybe work like the other User Preferences settings. When these settings are changed, you’re prompted with the option to apply the change historically for all users.