I've seen this mentioned on other threads, but haven't seen a fix. I keep getting the message not sent notification when I send and receive SMS messages. It just started this morning and I'm not sure why. Pretty annoying.
I was having this issue when I first got my phone, but I called Sprint and it was solved in a minute on their end.