The Microsoft Exchange Unified Messaging service cannot be contacted to play messages on your phone. Try again later. If this problem continues, contact your Exchange administrator or support organisation.Being that I administer our Exchange 2010, I got lumped with finding out why it wasn't working. It took a while to check certificates etc between Lync servers, the UM servers, CAS boxes and the O365 end points and they all looked fine. There was no error messages in any server logs either.
Interestingly, if I did the same "Play on phone" action from the Office 365 Outlook Web interface it worked meaning that at least from off site, the certificates were fine and everything was talking. After another look at the client with Wireshark, I noticed that there was no network traffic when you click the button which lead me to looking at the Outlook client. Testing a few hotfixes later and it seems that KB2880477 is the answer.
There is no mention of the issue in that KB but the version of the Outlook 2013 SP1 add-in "Microsoft Exchange Add-in"'s UmOutlookAddin.dll changed from 15.0.4569.1503 to 15.0.4629.1000 and the Play on Phone now works.