Ya encontre la solución, al tratarse de un backup realizado por otro dispositivo, este copió el nombre del ID del backup original y creo conflicto con el propio del dispotivo, en teoria, el error de Google Play debería dar a todos los que tengan el backup instalado...
SOLUCIÓN: Comprobar el ID original del dispositivo con la App gratuita de "Device ID", copiar la secuencia de letras y números que nos da "XXXXXXXXXXXXX" y con la herramienta "change android id ★
root" nos pedirá permisos, se los damos y cambiamos el ID actual (Del dispositivo de Flufy) por el original de nuestro dispositivo que copiamos anteriormente, nos pedirá reiniciar, aceptamos. Y todo debería ir perfecto, si queremos volver al ID anterior, el programa genera un backup automático en la SD, basta con reemplazarlo con este o titanium backup.
Descargar
change android id ★ root