Acho que você não instalou as duas dependências que o Spotify-notify indica no Google Code:
sudo apt-get install notify-osd python-indicate
Quando eu estava no Ubuntu 12.10 eu estava usando o script spotify-notify .py que torna o spotify compatível com botões de mídia e há uma notificação mostrando ao tocar uma música
mas no Ubuntu 13.04 não está mais funcionando existe algum pacote faltando ou qualquer solução que faça o script funcionar novamente
clique aqui para baixar o arquivo de script
Acho que você não instalou as duas dependências que o Spotify-notify indica no Google Code:
sudo apt-get install notify-osd python-indicate