I also have the same problem and it is not remedied by pressing the "New Text Message" button. This button does work and it works fine up until you press the "send" button. The Iphone will try to send the message but fails. If that same person I tried to text, texts me a message, I can reply and all my text messages go through fine from that point on.
I called my phone provider and they said that it is probably something with my phone. I'm glad to hear that I'm not the only one experiencing this problem. There's probably a good chance the problem will go away with a firmware update as this problem did not happen until I guess my latest firmware update.