I tried most everything on these threads throughout the betas, and nothing worked for me to get MMS going, even though I have a Family Unlimited messaging plan with AT&T. Tethering worked by updating the ipcc, but not MMS. Changing the settings manually always made the phone act strangely (ie, Visual Voicemail would stop working or be intermittent, or tethering would disappear).
On a lark, I decided to try something simple. On my fresh restore GM I had no tethering or MMS options showing. I updated the ipcc through iTunes, and then had the settings. Voicemail and Tethering worked, but MMS still stalled.
I took the SIM out, put it in my old Treo and tried sending a message. No go, at first, but on the third try, it started working. I put the SIM back in the iPhone and voila! MMS works! That was yesterday morning and still going strong. Tethering and Visual Voicemail work perfectly as well.
Note that I haven't touched the settings or made any calls to AT&T tech support.
I used this guide to modify the release version of iTunes to allow carrier updates:
MMS, Tethering working on iPhone 3G (IPCC Included) - Erodov