O comportamento que você observa indica que esses controles não estão implementados no seu cliente Spotify.
O controle da tecla de mídia por meio de um fone de ouvido Bluetooth é transmitido por meio do protocolo DBus MPRIS para o player a ser processado posteriormente.
Você pode testar isso executando o Rhythmbox, que deve ter uma implementação completa do padrão MPRIS (mas, sem dúvida, um Plugin Spotify não parece fácil de conseguir. No meu sistema, eu posso controlar a reprodução do Rhythmbox, incluindo botões de avanço rápido e retrocesso de um fone de ouvido Bluetooth. Mas eu não consigo fazer isso com um player que não suporta MPRIS (por exemplo, Audacious), onde eu também recebo o aviso que você postou na sua pergunta.
Você pode precisar de um reprodutor de mídia compatível com MPRIS que venha com um plugin do Spotify. Você pode tentar se Clementine atende às suas necessidades.
Infelizmente, no entanto, em 13.04 o plugin Clementine Spotify parece não ter suportado por mais tempo , então você precisará de uma versão anterior do Ubuntu.