El usuario borró mensajes pero sigue fallando.
En muchos feature phones HTC (Brew/Qualcomm), los SMS borrados van a una carpeta "Eliminados" que sigue ocupando espacio hasta vaciarla. La respuesta original lo explica bien: "tuve que ir a mensaje > seleccionar mensajes eliminados y eliminarlos. Si los eliminas siguen ahí hasta que las borres".
Si persiste, borra también borradores, enviados, y mueve multimedia a tarjeta microSD.