We recently got transitioned from the old BPOS (Exchange online) to Office365. Leading up the transition we were provided with a list of changes to make to our DNS to support Office365. After the transition we got everything working except the Lync 2010 client on Windows Phone 7, kept getting errors around being unable to sign in, can’t connect to the server.
Turns out there’s a CNAME record that’s needed by the WP7 client that Microsoft neglect to mention. This blog here had the secret sauce but basically we were missing this guy: