Bueno, pues como el móvil tiene ya casi dos años y muchas actualizaciones una encima de otra, siempre sin restalecer de fábrica porque todo iba bien, este fin de semana he decidido restablecer de fábrica, para hacer limpieza... Esta ha sido la solución, ya parece que funciona Google Wallet. Puedo añadir mis tarjetas de distintos bancos sin problemas, así que nada, doy por cerrado el tema.
Si a alguien le ocurre algo similar, espero que lo pueda solucionar.