Como resolver: Erro ao recuperar informações do servidor [RPC:S-5:AEC-0]

Tenho um Galaxy X com Android 4.2.2 que começou a apresentar esse erro chato, tudo começou depois de uma burrice minha.

O Android estava baixando atualizações de apps via 3G mesmo com a opção desativada para isso, como não queria parar, mesmo eu tendo setado novamente a opção e reiniciado o aparelho, desativei o processo que gerencia esses downloads no Android, dias depois precisei instalar um programa mas o download não acontecia, acabei limpando o cache do processo "Estrutura de serviços da google", só depois de ter feito isso é que lembrei que tinha deixado o serviço de download desabilitado, ai o mal já estava feito, após reiniciar acabei tendo o erro "Erro ao recuperar informações do servidor [RPC:S-5:AEC-0]".
Pesquisando pela net encontrei dois links:

[1]: http://www.techtudo.com.br/dicas-e-tutoriais/noticia/2013/07/como-resolver-no-android-40-o-erro-ao-recuperar-informacoes-do-servidor.html

[2]: http://www.androidpit.com.br/pt/android/forum/thread/557427/TUTORIAL-SOLUCAO-Erro-ao-recuperar-informacoes-do-servidor-RPC-S-5-AEC-0#p1630840

Tinha tentado a primeira opção como já tinha informado antes mas não deu certo, seguindo a dica de um user no segundo link, removi minhas contas Google do Android, abri a Play Store que me pediu email e senha, depois foi correr para o abraço, tudo funcionando perfeitamente.