I had the same problem especially sendin pics to people with Iphones. To send a pic to an Iphone you must use the stock message app and must put a caption along with the picture. For other phones handicent app works but it takes little longer for it to send sometimes and you will get an unable send notification but it goes threw in a few min because it keeps retrying to send on its own. Hope this helps
Text along with the pictures sometimes does the trick for me as mentioned above, but also try using a lower picture size Small (640x384) might do the trick because not every phone is 8 mp.