I know this issue is a month old, but we may have solved it last night on the unrevoked IRC channel.
I had the same problem, and it turned out it was because unrevoked overwrote my phone's carrier ID and it was using the MMS protocol settings for another company.
The guide here will tell you how to edit your BCID, but it doesn't say how to find the right one if you're already having the problem.
http://home.kennynet.co.uk/~kenny/bcid-fix.txt
unrevoked had changed mine to UTSI_005 when it was meant to be UTSI_019. I happened to know my correct one from my previous phone, and some versions of stock CDMA ROMs have a list buried somewhere in them.
If anyone is still having this problem, which is only likely to happen with people on carriers with outsourced MMS gateways like Interop, I'll see if I can get the list.