I've checked the apn lists here and elsewhere including vodafone.co.nz and they appear to be correct on both our phones. My colleague's phone is a "new" (refurb we assume) that arrived today and he's just updated iOS to the latest. Mine's up-to-date as well.
Has anyone else had or heard of this problem recently? Any suggestions?
For the record:
MMS Proxy: 172.030.038.009:8080
MMS Max message size: 308200
everything else is blank.