If you have an iPhone and have not had visual voicemail for weeks, it’s actually your fault, even if you didn’t know it. When you downloaded that little file to enable tethering, the maker actually messed up. The file from gizmodo had the Visual Voicemail APN set to wap.cingular, which is incorrect. It should be acds.voicemail. The fix is easy: go to settings>general>network>cellular data network and edit the Visual Voicemail APN as above to read acds.voicemail. Restart your phone and everything will work again.
NOTE: The fix above only works if you’re jailbroken and you have the package “APN Editing” installed. I think you can also expose this menu with unlockit.co.nz (but be careful, the normal profile they use for ATT US carrier, mms/tethering enabled has the wrong APN for vvm, reset it as above). I’m trying to modify the carrier profile from gizmodo to correct the issue in the first place.