I have the same problem, it's not a network issue. It only seems to happen to certail contacts and a second or two after the text is sent you usually get the "SMS delivered to ..." message pop up on the yellow message bar but then when you get back to the message in the conversations window it is showing as failed. On all the ones I have asked about the message did get through too.