Um cliente do Lync não faz o download direto do Adressbook. Pode levar algum tempo até que isso aconteça. Você pode alterar o registro para fazer isso:
reg add HKLM\Software\Wow6432Node\Policies\Microsoft\Office.0\Lync /v GalDownloadInitialDelay /t REG_DWORD /d 0 /f
A Microsoft tem um site maravilhoso Documentação do TechNet que explica isso com mais detalhes .