Eric brings out some excellent points, and the under-current is that as an busy practice already having challenges, adding/changing a key provider can amplify the problems.
I do wonder if their architecture hasn't kept up [from a plan/clarity point of view] with the systems growth and complexity.
There are some diagnostic nuggets that would helpful to understanding current circumstances, to wit:
<>are users logging in against the domain controller?(domain versus local password)
<>are users running as users without administrators rights?
<>what kind of traffic monitoring/shaping are you running at each location (e.g. MRTG, squid, Sonic, Watchguard, Cisco)
<>is there a plan for regular maintenance & patching?
<>is there a plan for regular scanning virus&HIPS checks?
I could go on, but I'm a recovering engineer, and I need to know my weaknesses.
With information like this you could have an off-line conversation with a systems professional, and provider that person a LogMeIn or join.me session to take a quick peak around the system.
My guess is that you need to team your local "boots on the ground" with someone with a more holistic perspective on multi-location architecture & system, and help them start being more pro-active in their work.
You'll need some mrtg (or similar) network traffic data, but I also wouldn't rule out network through-put latency from your local provider as being part of the problem.
