Same problem here. Been getting it all morning!
I'm having the same problem since yesterday or the day before.
tried restarting my iphone 4 with no luck.
I'm unable to sync playlists as well, same issue everyone else is having, 3GS on 5.1.1 using Spotify 0.5.4.13
Stared playlist unavailable for the last 2 hours. Only one song of the 600 seems to be available offline.
"There was an error communicationg with Spotify. Some tracks couldnt be made available offline. Spotify will try again later"
It works for me!
yipee, working now!