We got this message when we deployed Lync 2010 into our environment.
This is how we solved it.
1. On Lync 2010 Server, launch Lync Server Management Shell and run this command: Update-CsAddressBook -verbose
2. Wait for a few minutes and you should see these events in your event logs.
Event 21005 = Sync has started
Event 21010 = Sync has completed
Event 21056 = Details of the Sync
Event 21005 = Schedule for the next Sync
3. Because Lync client would randomly schedule the address book download at different intervals within a few hours; the Lync client can exhibit this same behavior. So if the steps above doesn't fix the issue then do the steps below
4. Run Regedit and navigate to HKLM\Software\Policies\Microsoft\
Communicator
5. Create/edit the DWORD GalDownloadInitialDelay and set its value to 0
6. Close the Lync Client and delete GalContacts.db and GalContacts.db.idx files form that PC. You can find those files in the following locations:
Windows XP: %userprofile%\Local Settings\Application Data\Microsoft\Communicator\sip_<the_username@the_domain>\
Windows Vista/7: %userprofile%\AppData\Local\Microsoft\Communicator\sip_<the_username@the_domain>\
7. Restart Lync.