I ran into a problem with MMS after I upgraded to iOS4 on my iPhone 3GS. Somehow, it was impossible to send MMS messages on the KPN cellular network. Searching the Internet revealed that I wasn't the only one.
The general consensus to solve this issue was a restore of the iPhone and not to restore old settings, but start from scratch.
After doing this, MMS still couldn't be sent from the iPhone, so time to do some more research. It turned out that KPN must have change the MMS settings, since my old MMS settings weren't correct anymore. So try these settings BEFORE you restore your iPhone. It might save you a lot of work and time.
Note: the following settings are for the Dutch KPN Network, and probably won't work on other networks / carriers.
Old Settings
APN: portalmmm.nl
Username:
Password:
MMSC: http://mp.mobiel.kpn/mmsc
MMS Proxy: 10.10.100.50:5080
MMS Max Message Size: 300000
New Settings
APN: portalmmm.nl
Username: kpn
Password: kpn
MMSC: http://mp.mobiel.kpn/mmsc
MMS Proxy: 10.10.100.20:5080
MMS Max Message Size: <leave empty>
Notice the differences? Anyway, with these new settings, MMS worked again.
KPN does have a page dedicated to the iPhone (in Dutch), regarding the Internet, and MMS settings. Just check those pages for the lastest settings.
I've updated the original page on my blog with the new settings.