After populating and publishing the LIS Database in Lync 2010 I had some lync clients that were automatically populating the location and some that were not.
I noticed the clients that were working were a higher version and found this link on MS Support
This is an issue in earlier clients and is fixed in cumulative update package for Lync 2010: January 2011. The clients that had the issue were on version 4.0.7577.0
I downloaded the latest Lync 2010 client update which was October 2013 at the time and this resolved the issue straight away!