Ok, I figured it out. After upgrading to either the 3.1 or AT&T's MMS upgrade, it caused a conflict with the tethering settings that I had downloaded from the help.Benm.at back in July. After removing that profile and reseting my network settings, my voicemail began working immediately. I did lose my tethering ability however but since I rarely used it all is well for now, or at least until I figure out how to make tethering work again.