Server up, bot not available

Our exchange server at work is up and running. The information store is mounted and everything in the manager seems to be working fine. Some users cannot connect to the server."Server unavailable" always displays even when reconfiguring outlook on the client. I noticed that when I try to look at some user properties on the active directory (using "AD users and computers" on the exchange server), it takes a very long time to do it.
Although some users connect OK, others were not able to connectfor days now.
Any suggestions.