I've been having this same issue for a LONG time now. I've read a lot of cures, I ended up messing with my APNs manually and got things REALLY cocked up. I heard that 8sms
would work better than the default messaging app and have been using that, but I still can't send MMS messages. I've pretty much given up at this point.
*** Sprint Samsung Galaxy S4, Stock rooted Touchwiz rom, Android 4.4.2 NAE (MF9 bootloader, no Knox), SuperSU V2.01, Busybox v1.20.2-cm9, KT-SGS4 4.4 kernel, PhilZ Touch 6.48.4 recovery ***
Leave me alone, I know what I'm doing!
(except when I'm totally lost...)