Voice mail in Outlook 2013 won't Play on Phone

We have users who are trialling Office 365 for their email but use an on-premise Lync 2013 phone system. When they get a voice mail in their Outlook 2013 (with and without SP1), there is a Play on Phone option that is meant to ring their phone and play the voice mail.

However, when they click on that, the following error pops up.

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.