As of writing today, my Android powered phone (Droid X) cannot send SMS messages to some people, but receive messages fine. This is because my address book has “+1” on some people’s numbers.
Solution: Add/edit a number without the “+1” – in a connected world, I don’t even bother to “save” phone numbers, they get synced to me from third party sources (facebook). In this case, synced in such a way that it won’t work.
By the way, I tried the stock Android SMS program and Handcent SMS, both have the same trouble. Quite a hassle, but such is technology/software. Sigh.