I had this same problem. I could send group messages to people that had iPhones, but when ever I tried to send a group message to people that don't have iPhones, it would never go through. I was searching and searching for an answer, and I finally found it.
I went to the Settings --> Messages --> Group Messaging
Turn OFF Group Messaging
Doesn't make sense, but it worked for me. Hope it works for you too.