Hade samma problem en gång. Gå in via iCloud kontrollpanelen i OS X / Windows och ta bort alla säkerhetskopior där och starta säkerhetskopieringen.
Löste det för mig, använder dock inte Spotify så det kanske är något specifikt där.
Men alltid värt att testa.