Is this happening for all clients or just one? If it's just one, try deleting your profile and setting GalDownloadInitialDelay to 0 as seen in this link: http://www.lyncfix.com/2014/01/19/the-address-book-is-preparing-to-synchronize/
If it's many, check your Lync Front End event logs for Address Book Service errors. Post any events or information you see. Try running update-csaddressbook from the Lync Management Shell and post any errors or warnings you see there and in the Lync section of the event log.