I have been tethering since the iPhone 4. And I'm on my second Android phone and still having no problems doing so. Although I was rarely doing it on the 4, and now pretty much use it everyday on Android.
One of the things we keep in mind in the Android community is that AT&T apps are BAD. If you're going to tether, but not be on a plan, you better not even think about using any of their apps, not even the myAT&T one.
I think the real problem here is the Visual Voicemail. Here are some of the standout permissions on Android: FULL NETWORK ACCESS, READ PHONE STATUS AND IDENTITY, CHANGE NETWORK CONNECTIVITY, RETRIEVE RUNNING APPS, VIEW NETWORK CONNECTIONS
The permissions aren't known on iOS, but I bet if you could trace all instances of network access that you would see similar happening in the background.