Usually, being on WiFI is the culprit. In all previous builds of stock Android and AOKP I had noticed problems sending MMS when on WiFI. This is going all the way back to the Nexus One. If I was on WiFi, and hit send for an MMS, it would fail 9 out of 10 times. It didn't matter if I disabled WiFi after, it still would not send. I would need to create another MMS and send it with WiFI already disabled for it to succeed.
Oddly, in AOKP Milestone 1 this problem has been fixed for me. I can send MMS while on WiFI now and it happens quick. However, my finace's Gnex is on the stock Verizon JB build and it still has problems sending MMS while connected to WiFi and she is always complaining to me about it.