So i have a jail broken/unlocked iphone 3g on 3.1.3 fw, and since i have had it i got mms enabled and working but up to recently, i have been getting the "The media content was not included due to a picture resolution or message size restriction"
You should contact your carrier, they may have updated APN settings for their customers and since you have set yours yourself, would not have pulled the update.
If you're using TMobile in the states, they have an iPhone department and can help you.