I had no problem sending texts to anyone earlier today. Suddenly, I'm unable to send to non-iphone users. What gives? I turned on the "use SMS if iMessage unavailable" in settings.
Also, try going to Settings - General - Reset and then select "Reset Network Settings".
This fixed the problem once it occurred for me, when I first got my iPhone. You could always take it to your carrier. Sending SMS is a big part of your phone.