It's funny how this is meant to be an "apple's" forum, where you might expect some help from them, and I've been through all the post in this thread and not a single answer is given by anyone from Apple. We all try to guess what's wrong and try this and try that with all the best intents to help each other, and Apple, NO, who cares!!
I tried all this stuff here to no avail, reset phone, start from new, turn this off, turn that on, nothing works. This all started on one of my 3GS phones after I upgraded to iOs 6.1.3. Before that everything worked fine. My iMessage seems to be working, it turns on, the "send" button does turn blue, but as soon as you hit the button, it turns green and goes out as text. Go figure. Having said that, it works just fine on the other phone and my partners phone too, none on 6.1.3.
You'd expect Apple to care more about their customers, especially considering the amount of $100's of dollars we pay for these restricted gadgets. As some said, I guess going Android is the best way.
Good luck to all!