I had this same issue on both of My Epic's. I brought the first one back and the guy mentioned doing an Update Profile and Update PRL. Both of which did not work. I was soo happy to get my new one thinking that the fact that my phone was rooted had something to do with the Text Messages getting stuck at the "sending" state.

I then cracked open my new one and was excited but as soon as I left the store I sent a text to realize that it was still stuck at the "sending" state again. I'm not sure what's going on either but it seems to happen more often than not now. The only true solution for me is to reboot my phone.