Of course, I had exactly the same problem, took me an age to get O2 working OK.
Set up two access points (Seetings>wireless controls>mobile networks>access point names>menu) with the following settings
Name: O2 Internet
APN type: default (actually type in default, don't leave it blank)
All others remain as "not set".
2nd access point
Name: O2 MMS
mms proxy: 18.104.22.168
MMS port: 8080
APN type: mms
Save and switch phone off and on.
It is worth noting that I had an iPhone tariff as I changed my iphone for a magic. I spoke to O2 about it when it didn't work and they enabled MMS, still didn't work. We solved it by changing my tariff to a normal O2 tariff, same cost and freebies, just a different name.