Need help? Check out Spotify Answers for solutions to a wide range of topics.
Advertisements and features like browse can use up data as well. Does Spotify have the space and been given the time to build a cache? Definately shouldn't be at 500 just from spotify though.
From the Android data usage screen. My carriers app pretty much agrees with the usage as well. I'll try a clean install.
The app info page also shows that the app has 385MB of "data" and the cache is 3.6MB.
What would all that data be? None of my saved music is available in offline mode.