The debian package does not state all the packages Spotify depends on.
In the 0.9.x series, this caused the problem with libgcrypt11. Recently I faced a similay problem with libssl1.0.0 in Debian Stretch (testing); libssl1.0.0 was replaced by libssl1.0.2 in a system upgrade. I could no longer run Spotify because libssl1.0.0 was missing.
Should Spotify state all its dependencies (libssl1.0.0 in this case), libssl1.0.0 wouldn't be remove as part of the upgrade process (to the package manager, no one dependen on libssl1.0.0 so it was safe to remove it).
This is a request for the Spotify Linux team to improve the information in the Debian package so (Linux) user don't face similar problems in the future.