I just went through a very similar issue. In my case it
was directory access. We had a scheduled outage window for
maint and whe the servers cam back online teh exact same
results were appearing.

It turned out in the end that one of the DC's/GC's had a
corrupt copy of the Active directory. For all intensive
purposes the domain controller apeared to be in perfect
health but once it was turned off (temp) and the DS access
allowed to go elsewhere for its services everything was
working again.

Hopefully you have more than one DC in that site you can
test against.

..Dan