I've now got a response from Spotify on this. They say it is a known issue and they are working on a fix as a priority.
I also mentioned in my email response that the app seems to crash regularly and the login screen sometimes gets stuck. None of these issues occured in the preview version so I can't understand how it has gone so badly wrong!
Anyway, he said that a temporary workaround was to turn of the phone, remove the battery for 30secs, and try again. This did not work for me. He also asked if I had an 3rd party music players on my phone, which I don't as I have tried from a factory default phone.
All in all, the app is currently unusable until a fix is made, and so I'll have to use the preview version for the moment. It's all quite frustrating that we have this when the i-phone has had yet another update to include spotify radio!!
I have exactly the same issue. spotify does not play the next song if it is streamed (there is no sound, but progress bar shows progress). Downloaded playlists work for me. I also have uninstalled the app and reinstalled again. Taking out the battery does not make sense to me and cannot be the solution..... Android 2.3.4 on LG Optimus 2X
Please, please fix this as soon as possible.
The app and so the payed account is then useless to me...