The title might confuse you, as many of you might have heard that everything is setup correctly in Office 365. I found that the external communications was disabled for my tenant for some reason.
While checking out the settings for Lync Online, I found the status for external communications to be Enabled, but the status was listed as disabled for all my domains, including the onmicrosoft.com one.
In order to fix it, I had to disable the external communications using the Disable button. That changed all my domain status to Connection Pending.
It took more than a day for me to get all my domains enabled for external communications.
Next time you play with Office 365, check all the settings. Don’t just assume that everything is setup correctly & will work out of the box . I learned this the hard way while setting up my on-premise Lync to federate with Lync Online, covered here. I was troubleshooting the on-premise deployment, while the problem was clearly with the Office 365 setting!