Lync clients require up to 60 minutes to sync the address book, so the message might be normal.

please check these resources for more information and troubleshooting:

http://blog.schertz.name/2010/09/updating-the-lync-2010-address-book/

http://blogs.technet.com/b/nexthop/archive/2012/06/21/lyncmd-troubleshooting-the-lync-2010-address-book.aspx

Hi,

Please try this:

Update-CsUserDatabase

Force to immediately update the changes performed on Active Directory objects into the back-end SQL database for the pool.

Update-CsAddressBook

Execute Update-CsAddressBook to trigger the Lync Server to synchronize current Active Directory information in the SQL database into the downloadable client and device address book files.

If the issue persists, please try to remove lync profile and try to sign in again.