Microsoft Exchange Server is unavailable

We have a few users that get the above error message when they try to open
their outlook in the morning, however if they hit retry once or twice they
eventually get a connection to the exchange server. It started after I
installed office updates on their computers. This problem is intermitant and
does not occur every day. I added the user to the NT Authority\Authenticated
user group in Admin tools\ computer management window. It did not help.
Please tell me how to fix this problem.