>I can't find any commonality between the users having problems, or between those that aren't.
Check the clocks on the workstations and servers, make sure they are within a minute or two, have the same date, and time zone. The most frequent problem here is the Kerberos reliance on time. The spec calls for all clocks to be within 5 minutes, but much closer is much better. The Microsoft default time adjustment periods are ridiculously too long, so changes in defaults may be necessary to prevent drift. Failing that, regenerating certs may help. Daniel Sichel, CCNP, MCSE,MCSA,MCTS (Windows 2008) Network Engineer Ponderosa Telephone
