I am on an iPhone 6 running iOS 10.2, my phone is jailbroken but o have no tweaks that inject into Spotify. I have tested this on all 8.5.x versions and it does not exist on 8.4.x.
When I shuffle all of my songs, the song and album artwork correctly load for the first song, but then if I click the next song button, the song changes but the album art stays the same as the first song. I can continue pressing the next song button and the album art will still be the first song, there is no animation or anything, it simply does nothing. This does not happen when I slide to go to the next song, but I prefer the button.
Since I am jailbroken I may be of assistance since I have the ability to downgrade apps but that is up to the developers.
Thanks for making a great app and I hope this bug gets fixed. Please email me and I can provide more details of necessary.