Mais um erro chato que acontece quase toda vez que o Google resolve promover uma grande atualização na lojinha. Isso já está virando vício.
No Android 2.3.x não notei esse erro e pelo que andei lendo na web, é provável que seja praticamente exclusivo, senão exclusivo, da versão 4.1.x. Não tenho mais nenhum Android 2.2< ou 4.0.x aqui para comprovar. No 4.2.x não aconteceu.
O erro da vez é o RPC:S-5:AEC-0, soluções são várias, mas parece que nenhuma é garantida para todos os usuário (como sempre).
Primeiro tentei reiniciar o servidor de licenças (su && drmserver&), sem sucesso:
Depois tentei limpando cache e dados do Play e do framework... nope.
Última tentativa antes de partir pra ignorância: desativei backup e restauração, removi a conta do Google, limpei cache e framework, reiniciei, adicionei a mesma conta novamente e... sucesso :)