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.
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