Back up all the songs.
Clear the thumbnail cache of Music. (Music folder of Phone memory).
Use Windows Phone's desktop app to sync the music.
If you want to copy via Explorer you should rearrange your music
folder structure as Music Folder > Artist Folder > Album Folder >
I could be wrong (or it could be wishful thinking), but I cant say I've noticed gaps between tracks in Spotify.
Granted, it's not just a player, and granted it's a bit pants on WP, but it can play local files in addition to streamed.