Could you please change the dependencies on spotify-client from "libavcodec53" to "libavcodec53" or "libavcodec-extra-53". The libavcodec-extra-53 library is essentially just an extended version of, and replaces libavcodec53.
Found out that my issue arised from ubuntu seeing recommended packages as dependencies. If I install spotify-client-gnome-support I can get arount this.
