Well, I finally solved my own problem. I was checking the tracing log and I noticed the below entry:
ms-diagnostics: 1013;reason="Significant time skew detected during authentication";source="(OCS Server)"
I then went to one of my domain controllers and checked the time. It was 8 minutes fast. Once I corrected the time, communicator logged right in without a problem.
Not all domain controllers had the wrong time, so that explains why rebooting sometimes fixed it.