Aunque borre mensajes, música, fotos, el error sigue y no deja usar funciones (contactos, etc.).
Los mensajes (SMS, MMS, correo) se almacenan por defecto en la memoria del teléfono (C:). Cambie la ubicación a la tarjeta de memoria:
Esto mueve la base de datos de mensajes a la tarjeta SD, liberando memoria C: y resolviendo el error.