MMS Working w/iPhone 3G, OS 3.0, Carrier File 5.1

Note that this will only work if you're among the folks that have had AT&T remove the account level MMS restriction. They are rolling that out now, so if you're not ready yet, you will be soon.  You'll be able to tell that you're ready, because there will be MMS configuration options under "Settings > Messages".  You'll also have a camera button in your message window, from which you can choose a picture. Once set, it may work out of the box for you, but if not, you may need to enable an extra set of MMS carrier configuration options.

Here's how:

Mac OS X: (This will allow you to load a carrier file, as opposed to just a phone OS update file)

1. Close iTunes if it is open
2. Start Terminal (Applications > Utilities)
3. Run the following command: defaults write com.apple.iTunes carrier-testing -bool TRUE

Grab the AT&T 5.1 carrier file from here:
Carrier Update File

Connect your phone to iTunes, highlight the iPhone device in the left-side pane and hold down the OPTION key while clicking "Check for Update".  That should allow you to browse to the carrier file you downloaded, and open/choose it.  You'll see a message that the carrier file is being updated.

Shut the phone off, and turn it back on.

Navigate to settings > General > Network > Cellular Data Network (that option will be new as a result of the carrier file update).

Configure the MMS settings like so:
 

Shut your phone off, and turn it back on.  That should do it!