Since update 0.9.0 the cache location resets every time you exit the app. This has two side effects: Any content you had downloaded before 0.9.0 is gone Any users with a small primary hard disk are unable to download tracks
You can now download the latest version from spotify.com; this will resolve this bug.
We have started rolling out version 0.9.0.129 to users and can confirm this bug is resolved.
If you don't have this latest version yet, do not worry. It will reach everyone soon.
Pro tip: log out and in of the Spotify app around the time of a new release; sometimes this triggers an update.