OST / Offline address books Problem

Not sure if these 2 problems are related…
4 or my many laptop users including myself can not use Outlook Offline through OST file. It is set to synchronize upon closing. The synch log shows everything synching, but then gives a “Terminated in Error” at the end. I have tried synching manually. On the server end, several times during the day I get an event log (ID 5004) that says: Generation of offline address books in complete. Result: The attempt to log on to the Microsoft Exchange Server failed. Microsoft Exchange Server Information Store ID 8004011d-0512-00000000″.
Because many laptop users are able to use their OST’s just fine, I’m not sure that they are related problems. As time is hardly becoming available to do the research here, thought i’d try asking first. Any help? TY!