If you have the below box checked, and your DNS records are set up properly (_sipfederationtls_.tcp.sipdomain.com) then it should work. If not, please contact Office 365 support.
DNS Help: https://support.microsoft.com/en-us/kb/2566790

Please remember, if you see a post that helped you please click "Vote" on the left side of the response, and if it answered your question please click "Mark As Answer".
SWC Unified Communications This forum post is based upon my personal experience and does not necessarily reflect the opinion or view of Microsoft, SWC, their employees, or other MVPs.