Sometimes we get this one through to escalation services:
"Instant Messaging isn't available right now. The Contact List will appear when the service becomes available"
It's a classic which has a very simple solution (if its that problem and not something else which could be very bad).
Usually its a new tenant on O365, a vanity domain (i.e. contoso.com not contoso.onmicrosoft.com). And the DNS records have just been created. That is the key. OWA is a trusted application, it is in the on premise version and it is in the cloud version. In order to use IM the vanity domain must have its federation DNS record:
Of course if you are on a P plan and your nameservers are pointed to Microsoft then this isn't a problem. At this point you should contact us at support or have a look at the forums (http://community.office365.com/en-us/default.aspx) to see if this issue has come up before. It usually has and usually if can be put down to an issue with DNS record propagation, or in other words, it might take more than 48 hours for your new DNS records to be spread amongst the DNS servers on the planet.
One other word of advice, make sure that the port is set to 5061, I've seen loads come through with 5016 or other mistyped forms. I've done it myself, its very easily done.