I've had the same issue with the voicemails from my Asterisk box also.

If you have access to the voicemail system, try changing the codecs. I followed this post and it's working perfectly now:

http://talk.maemo.org/showpost.php?p=555304&postcount=6

Cheers!