Erro: não a espaço no dispositivo

Ola galera, a muito tempo não peço ajuda em um fórum mais não achei a solução.

Meu celular começou a apresentar a mensagem "não ha espaço suficiente no dispositivo" quando vou baixar ou atualizar um app. Detalhe é que eu apago 1 app. Pequeno e então consigo baixar um app. Grande, como se ouvesse um limite.

Tenho mais de 500MB de espaço interno e 58GB no SD.

Já tirei o SD, já limpei o cachê, já reinstalei o playstore, já exclui a conta do google e nada, se alguém puder me ajudar eu agradeço.

— alterado em 24/06/2015, 12:38:27