¿Cuales tenias y en que orden exacto? Te digo por que yo las he tenido puestas hace poco, mas o menos no se, 15 días aproximadamente, y me han funcionado siempre perfectamente.
Si pones una queja al menos aporta información.
Como hipótesis bien fundamentada, que igual me equivoco, pero es hipótesis razonada, el tema puede ser el siguiente. Los DNS de teléfonica, que por aportar un detalle interesante para mas adelante, no tienen ECS por que no lo necesitan, te habrá enrutado hacia algún servidor cercano a ti del CDN usado por Spotify que esté dando algún leve problema, que se manifiesta como dices.
Al cambiar a Cloudflare, que encima no tiene ECS, aunque poca cosa en la práctica pero te habrá cambiado el rutado y lo habrá variado un poco, con lo cual ese problema que dices ha dejado de manifestarse. No creo que te haya enrutado hacia fuera de España, que por poder podría ser pero a tanto no creo, pero te ha variado un poco el rutado hacia otro servidor.
Si pruebas dos DNS resolviendo hacia un CDN exactamente no tienen por que resolver lo mismo ambos.
Es decir, por si no ha quedado claro, el fallo estaba en Spotify.
Bueno, y eso suponiendo que el fallo no esté directamente en tu dispositivo, y que lo del cambio de DNS haya sido casual.