My life's too short to wait for the **bleep**tards at Spotify to fix their **bleep** app. I can see people are still commenting on this issue, so it's obviously important to us users. For what it's worth: My solution was to buy a ChromeCast Audio. It's relatively cheap and it Just Works. This is the closest to a working solution as it gets.
@MichaelW thanks! Tried reinstalling (following guide) both devices, no success.. Can even control PC Spotify (running beta).. Dunno what's up with second Android (rooted, running Cyanogen 11-20140925) device tho :(