Just updated Spotify (1.0.77.338.g758ebd78) from third party software, and apparently there is a new dependency (curl-gnutls) that was missing from my installation.

ldd /usr/bin/spotify | grep curl
/usr/bin/spotify: /usr/lib/libcurl-gnutls.so.4: no version information available (required by /usr/bin/spotify)
libcurl-gnutls.so.4 => /usr/lib/libcurl-gnutls.so.4 (0x00007f1aa67cb000)