Just downloaded the latest app (don't know how to check for exact version number).
App no longer shuffles songs. Clciking the shuffle icon turns it on and off ... but shuffling ...
Hey @MarathonMax! Welcome to the Spotify Community. ^^
Have you tried reinstalling your app? If not here's a step by step tutorial.
Let me know if that helps, thanks! ^^