Seems most phones only work with one APN setting for combined Internet and MMS, well it does on my Hero any way. The settings further back in this thread may work individually but for the proper settings type in this under your APN settings.
This worked for me so you may as well copy exactly what I did.
1. Delete all of your existing APN settings and restart your phone.
2. Input these APN settings:
NAME: O2 UK Postpay
PROXY: <Not set>
PORT: <Not set>
MMS: PROXY 126.96.36.199
MMS: PORT 8080
APN TYPE: <Not set>
Press 'Menu' and select 'Save'.
3. Now restart phone again.
4. Switch on 'Mobile Network' and test it. Should work perfectly!!!
As mentioned before on other threads in order to send/receive large images via O2 you may have to use 'Handscent' but I have not tested it yet.