There are some required changes to get AutoDiscover for Lync Mobile to work with Office 365 in DNS. Create a CName entries for your Office 365 domain:
lyncdiscover CNAME webdir.online.lync.com (i.e. lyncdiscover.yourdomain.com resolves to webdir.online.lync.com)
You can find out more about the network and DNS requirements of Lync for Office 365 here (this in addition sip and srv entries): http://onlinehelp.microsoft.com/en-us/office365-enterprises/hh416761.aspx
Of course, if your an Agile IT customer, we take care of all of this for you. Find out more athttp://AgileIT.co/AgileAscend Update – Users that have their Lync Address using x.OnMicrosoft.com may have issues logging in using Lync Auto Discover. You can circumvent the DNS requirements by turning off “Auto-detect services” and setting the external discovery address:
Note - You can leave the internal discover address blank.