If your phone is on Android 4 then this is because it is unsupported - see http://community.spotify.com/t5/Spotify-Ideas/Spotify-needs-to-support-Android-3-Honeycomb-Android-4...
Otherwise it's just another common foible of the app that we're waiting to be fixed. Normally to get around this issue I delete the /Android/data/com.spotify.mobile.android.ui directory from the SD card. This will remove all your synced playlists, but it works for me every time
----------------
Listening on Windows, Android and Sonos. Tweeting it at @davelicence
