I just upgraded my Droid (sams gal s2, Spotify premium) and now it seems that Google search has the power in Spotify also.
I am no longer able to use the search option either on tracks, artist not album. The search field looks like google with the Mic on right side, search field in the middle and a Spotify logo with a < on the logo's left side.
This sucks as I may not play other music than I allready have in my playlists...
Any bright heads out there with a solution?