Since upgrading our Exchange 2010 servers to SP3 the Play on Phone feature for Voicemails handled by the Exchange UM server has stopped working. When you click the button it generate an error:

The Microsoft Exchange Unified Messaging Service cannot be contacted to play messages on your
phone. Try again later.

Nothing appears to be logged in the event logs on the UM server, it just doesn't work. Voicemail itself is still working fine and being delivered to the appropriate person.

Anybody with a similar setup, Exchange 2010 SP3 UM and Lync 2010 seeing this behaviour or know why it might be occurring?