I've got the same problem with my Onkyo TX-8050 reciever. I noticed in the playlist on my desktop that the tracks that aren't synchonised don't have an icon in the download column (this column is only visible in a playlist). For example see the track "born in time" form Eric Clapton. I find this very strange because all the other tracks from this CD synchronise flawlessly.
In your case it could also be possible that you use tracks from your Itunes or mediaplayer library in your spotify playlist. Those are locally stored tracks and only locally available. Those tracks are marked with a music-notes-icon in a dedicated column which is visible in playlists. The solution is to find the same tracks in the spotify library and ad those to your playlist.