This looks like a reasonable explanation.

The new app is signed by "CN=Spotify, OU=Android, O=Spotify, L=Stockholm, ST=Stockholm, C=SE", the old was signed by "CN=Anders Bond, OU=Mobile, O=Spotify, L=Stockholm, ST=Sweden, C=SE". The new key was generated on 2014/05/24.