Eu tentaria remover o Spotify do iniciador e adicioná-lo novamente. Como alternativa, você pode criar um arquivo Spotify.desktop
com o seguinte conteúdo:
#!/usr/bin/env xdg-open
[Desktop Entry]
Version=1.0
Type=Application
Terminal=false
Exec=/usr/bin/spotify
Name=Spotify
Icon=/opt/spotify/spotify-client/Icons/spotify-linux-512.png
Você deve conseguir arrastar esse arquivo diretamente para o iniciador a partir do navegador de arquivos.