Has anyone else had this issue? It all started after the GDR3 update I think. Now I am on the latesting Windows Phone 8.1 preview update that came out yesterday (May 14, 2014).
I haven't experienced the issue yet because it's only been a day, but historically the issue pops up when the phone's been on for a day or so.
What happens is I try to reply or send a SMS and it says "Failed to send" and the icon for Messages becomes a sad face. The only way to reliably fix it is by restarting the phone.
Update (7/24/2014): Still receive issue even with latest Windows Dev 8.1 preview. OS 8.10.12397.895