Hello,
I just updated to 3.1. I don't mind the loss of tethering (I tried it out for fun but never used it), but my Visual Voicemail is broken now. The option I used to use to fix it (Setting->General->Network->Cellular Data Network) no longer has an option for Visual Voicemail APN, only Cellular Data and MMS. I tried resetting network settings to default and nothing changed.

Anyone know how to fix this?

I have the same problem. APN option has disappeared, no multimedia messages going through, and no voicemail going through.