Same issue here. The message popping up that there is no space left. However, the sdcard is and internal memory are both nog full. Running Cynogenmod for SGS4, Android 4.4.2. The SD is used, verified that, but it stops with 50+GB available.
Yesterday it stopper after 21 tracks. But it could be that 100 songs sync and then the sync errr appears stating that the device had no space left. Currently running spotify 22.214.171.124 on Cynogenmod 11, Android 4.4.2. I am 1sure the SD is used because there the offline files are stored.
I'm having exactly the same issue as you on CM11 on a GS4 too. Have plenty of space available on Internal and External SD cards, I know it's now using 3.3GB of space with approx 630 tracks synced so far. I can sometimes get it too sync a couple more tracks if force close Spotify and restart, though this only happens occasionally I usually end up with the error message.
After the push update today, May 30th 2014, I am no longer able to store my offline music on the external SD card. My smal internal card on my Samsung S2 is already almost full already, so downloading to it is impossible, as it gets full after just a few songs.
Please make it possible to store music on the external SD card again, or let me move the whole app to the external SD card.
Or else I can no longer use Spotify, as I almost only use it while travelling or in my car. There are alternatives, but I prefer continuing using Spotify if you fix this.
I had the same issue two days ago. After upgrade the app android showed up an storage space warning when I was downloading offline songs then I unistall the app but it wasn't enough. This is what I did:
I deleted the spotify cache and save data (Spotify app -> settings -> Delete cache an saved Data).
Android Settings -> applications - > (look for Spotify app) - > "Clear data", "Clear cache" and "Force stop"
Delete Internal Storage - > Android -> data -> "com.spotify.music" folder If exists
Uninstall Spotify App
Make sure that you have enough space in sdcard
Install Spotify again
Select a playlist which has few songs and make it offline
Check Internal Storage - > Android -> data There mustn't be "com.spotify.music" folder