It's a bug in their Packages file:
Depends: gconf2 (>= 2.12), spotify-client-qt (= 1:0.5.2.84.g6d797eb-1)
Depends: libasound2 (>= 1.0.14), libc6 (>= 2.6), libqt4-dbus (>= 4.5.0), libqt4-webkit (>= 4.5.0), libqtcore4 (>= 4.5.0), libqtgui4 (>= 4.5.0), libstdc++6 (>= 4.0.0), libxss1 (>= 1:1.2.0), usbutils, libssl0.9.8
Recommends: libavcodec52, libavformat52
Look at the dependencies for 'spotify-client-gnome-support'. It says "spotify-client-qt (= 1:0.5.2.84.g6d797eb-1)", but the version that's installed is 1:0.6.2.291.gcccc1f5.116-1...
The line should be: "spotify-client-qt (>= 1:0.5.2.84.g6d797eb-1)"
You could create your own repository, or just don't install spotify-client-gnome-support... The latter worked for me ;-)
Found this on their forums:
Mathieu Bérard 3 months ago
The functionality provided by spotify-client-gnome-support was integrated in spotify-client-qt with version 1:0.6.1.309.gb871a7d-1
You can just first remove spotify-client-gnome-support and then upgrade to spotify-client-qt 1:0.6.1.309.gb871a7d-1