The other day I found this little issue in a deployment

We enabled UM for pilot users, and everything worked fine. But when we tried to play voicemails from an iPhone, it did not play the message. We tried with Android Phone and same error.

Solution:

We executed the following cmdlet to change the audio codec to MP3.

Set-UMDialPlan -Identity MyUMDialPlan -AudioCodec MP3

With this change, both devices could play voicemails

I hope this will help you