Microsoft Lync 2010 cannot connect to Lync Online service through a proxy firewall when Lync 2010 is in automatic configuration mode.
This issue occurs because the Domain Name System (DNS) Service record (SRV) for the Lync Online service is not resolved.
To resolve this issue, install the following cumulative update:
2496325 Description of the cumulative update package for Lync 2010: April 2011
Microsoft has confirmed that this is a problem in the Microsoft products that are listed in the "Applies to" section.