Pues como dices, deberías hacerle una limpieza: un reset de fábrica y formatear la SD. Ésto último podrías hacerlo primero, ya que de a veces de tanto instalar y desinstalar apps, se van quedando restos en la sd (similar al pc cuando llevas años instalando y desinstalando programas) y quizás puedas ahorrarte el otro.
Yo haría eso, formatear la sd (guardando lo que necesites, claro), y un reseteo de fábrica.
