Ciężko powiedzieć. Nie widziałem.
Standardową radą jest oczywiście wipe. Pod warunkiem, że chcesz stracić wszystko, co masz zapisane na telefonie. Oczywiście, możesz wpierw zrobić backup większości rzeczy.
Ja bym raczej spróbował zainstalować zewnętrzną aplikację do obsługi wiadomości.
Np. najpopularniejszego Handcent SMS, albo nowego, ale coraz popularniejszego GO SMS, oba darmowe na markecie.
Ale zewnętrzna aplikacja to ominięcie problemu, nie rozwiązanie go...
Jeśli masz roota, to możesz spróbować wywalić aplikację systemową i zainstalować ją od nowa.
W ostateczności - ale nie sądzę, by do niej doszło - pozostaje reinstalka softu.