Acabei de instalar o Spotify do Ubuntu Software Center para replicar o seu problema e, na verdade, quando abri-lo, não há ícone, apenas um ponto de interrogação, como você pode ver na minha primeira imagem.
Pararesolveresseproblema,fizoseguinte:
Editeessearquivo~/.local/share/applications/spotify.desktop
comqualquereditordetexto(porexemplo,gedit,nano,vim),useigedit,entãoocomandoera:gedit~/.local/share/applications/spotify.desktop
PesquisealinhaquedizIcon
ecoloqueoseguintetexto:Icon=/home/<yourUsername>/.cache/gnome-software/3.20/snap-icons/4e763d64d7d04a3b072fcb90e3798530916c6b8a-spotify-linux-256.png
Épossívelque,emseusistema,onomedoíconesejadiferente.Nessecaso,bastaacessarapastaeverificaronomedoícone.
Sobre a pesquisa no aplicativo, ele funciona perfeitamente para mim. Tente desinstalar e instalar novamente para ver se funciona.
Espero que ajude, boa sorte e curta sua música!