Had the same problem yesterday. I was on the phone with Verizon for about an hour, mostly with level 2 support, who called Nokia, they didn't have an answer, then he escalated it further. I posted it here, and over on WPCentral where someone else had the same problem. Then someone else saw our post, said he had the same problem, and fixed it by restarting the phone. Try that.
I saw this post and the one you did on wpcentral, but i am still having this issue.
I have restarted my phone 3 times, one time by pulling the battery, then i removed the sim card and replaced it. Then i went into my mms apn settings and try to apply what they had for iphone and droids. Still nothing.