I remember Visual Voicemail being broken for me back when I used to use Mint as well.

I switched to US Mobile on Verizon's network and it works perfectly fine.