Voicemail Issue: Remotely checking

I’m having a problem with checking voicemails from remote locations. Clients still receive email notifications, and the .wav file is intact. If you check from one of the Aastra phones that are connected to our TFTP server, there are also no issues.
The issue is when we try to have them check from remote - homes, using cell phones, etc.
Hitting play on the email, makes it just auto hangup.

[Jun 4 09:42:37] WARNING[85361] app_voicemail.c: Playback of message /var/spool/asterisk/voicemail/…/msg0000 failed

[Jun 4 10:50:42] WARNING[85361] app_voicemail.c: Playback of message /var/spool/asterisk/voicemail/…/msg0000 failed

[Jun 4 10:54:25] WARNING[85361] app_voicemail.c: Playback of message /var/spool/asterisk/voicemail/…/msg0000 failed

[Jun 4 10:55:41] WARNING[85361] app_voicemail.c: Playback of message /var/spool/asterisk/voicemail/…/msg0000 failed

Asterisk version 1.6.2.13
What other info would help with this? Any idea how I can further look into it?

Can you show us the link that is under the play-link in the email?
regards,
Tom

Oddly enough, it was the network configuration. Replaced the router - resolved the issue.
Strange but probably something to do with that we use port 15000 on RTP