After a little bit of testing, I think I might have discovered something.
If you send to the phone # with a +1 in front, it will give you SMS errors. If you send to the person without the +1, it works FINE.
I think you are probably right, if I remember correctly, I stopped putting the 1 in front of contact numbers a long time ago for this very reason (i.e. it's not just an android thing).