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.
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.