El problema está con la base de datos que crea el Mms.apk para guardar los mensajes. Se me ocurren 2 casos:
- Que por una actualización sin wipes se hayan mantenido los datos de una versión muy antigua y por eso no funcione
- Que hayas restaurado SMS y MMS desde Titanium o similares
En cualquier caso, la solución debería ser un wipe de data.
EDIT: quizás no sea necesario ser tan bestia. Si entras en Ajustes > Programas > Mensaje > Borrar Datos, también debería arreglarse.
