Have you tried a network reset?
Goto Settings>General>Reset>Reset Network Settings
Your iPhone should then re-boot. You will have to re-enter any WiFi passwords you may have already entered. No other data will be lost though.
Also make sure your APN settings are correct for MMS
Goto Settings>General>Network>Cellular Data Network
For Pay Monthly O2 MMS make sure you have the following settings:
APN = idata.co.uk
Username = vertigo
Password = password
MMSC =
http://mmsc-ac.mms.o2.co.uk:10021/mmscMMS Proxy = 193.113.200.195:8080
MMS Max Message Size 2097152 (increasing this figure to 5000000 sometimes also helps)
See
this page if you are on PAYG or Pay monthly but not on an iPhone tariff for the correct MMS settings.
If you do need to change any of these settings, you need to turn off your iPhone completely and turn it back on for the settings to take effect.
Even if these settings are correct, it's always a good idea to completely re-boot your iPhone as this alone often fixes such issues.
O2 where having system wide MMS issues yesterday morning, but I believe this has now been fixed.