Lync is experiencing connection issues with the Exchange server

Hi, We are using Lync 2010 for our online meetings both in internal and external client laptops/PCs.
However, when an employee tries to connect for an online meeting from the outside office, he gets a connection error with the Exchange Server (see screenshot below).
It seems the network connection is working fine since he can send/receive emails.
Any advice on how to fix the problem?

Lync
Lync is experiencing connection issues with the Exchange server. Lync will attempt to repair the connection until it is fully restored. History, voice mail, and Outlook-related features might be unavailable or out of date until the connection is restored.
