There change "Image size" to "Large" and "MMS creation mode" to "Guided" (or "Free").
If that's not enough, then you're hitting a limit set by your operator on their servers (their MMS-C, Multimedia Message Service Center). Call O2's customer service and ask what kind of limits for MMS they have defined.
There are options in the MMS settings for small, large and original. I'd try setting it to original if you haven't done so already. If you have, erm, that's me all out of ideas.
That I already explained in the first reply to this thread. Apparently it isn't/wasn't enough, so it must be either an O2 specific phone software (firmware) limitation, and not network related, if the device complains about the size even before sending the message.