Just as an addition to what Per mentioned, this issue has come up before when the phone has had no SD card inserted or the SD card has been corrupt. Could you confirm that you have an SD card and do a check on it.
Also, I note that the 5512 has a particularly small screen (320 x 240) - could be that spotify doesn't support this resolution.
Listening on Windows, Android and Sonos. Tweeting it at @davelicence