Have you tried a clean reinstall?
If you downloaded all songs from Spotify (and not your local files), this is definitely not a liscencing problem.
Please note that there is a setting called "sync over cellular" and if that's not turned on your music won't sync over 3G/4G.
Make sure you have enough space in your device. Spotify won't start synching normally unless you have 500MB-1GB of free space.
Check the Firewall - this might also be the cause.
Let me know if any of this helps 🙂