Spotify have changed the key used to authenticate their Linux repository – meaning you will need to update it inorder to continue getting updates.
Unless checking for system updates using the Terminal, you won’t be warned about the change. Ubuntu’s Update Manager application will continue to ‘update’ as normal, but not give any indication that there is an error.
The issue only affects those who have added the official Spotify for Linux repo to their Software Sources. Users of Spotify via WINE are not affected.
Leaving the error unfixed will mean that Spotify updates will not be detected, downloaded or applied.
The Fix
Fixing the issue is simple:
1. Open a new Terminal window
2. Paste the following command
sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys 94558F59
Spotify Forums, via Sam Osborne