Just because you have many users doesn't mean you can't take one test workstation and do some tests such as clean install or install SP3. Once you narrow down the problem or get a fix, you can think of deploying more widely. I doubt you have deployed a solution which declares one variable and instantiates it and does nothing else on all your users' workstations. If this sort of suggestion doesn't help, you should consider going to esri support for a definitive answer, this is just the forum, we are users too. But if it works at SP3 or SP4 or even 10.1, chances are they will tell you to go to that version.
