Visual Voicemail had been working fine until recently. When I launched it, it gave me a message that the account was tied to another phone, and my only option was to reset it.

This led me to re-initiate the VVM setup process. It repeatedly failed on 2G/4G/Wifi. Finally, I came across a post online which solved the issue for me.

The new T-Mobile My Account app is where I found the problem with interference for it to not connect to the server if using ICS not sure about others. Clearing data and uninstalling updates to this app T-Mobile My Account resolved the issue with Visual Voicemail right away.

To do this:

• Go to Manage Apps | All
• Select the T-Mobile My Account app and uninstall updates for it
• Go to the Visual Voice Mail app and clear data