Eu não sei sobre clementine, mas tanto o rhythmbox quanto o banshee suportam esse tipo de integração com um plugin. Eu não uso banshee, rhythmbox ou clementine, mas pelo que me lembro, acho que o rhythmbox e o banshee possuem um plugin de integração de mensagens instantâneas em sua preferência. Se você não consegue encontrá-lo:
aqui está o plugin de status para banshe
aqui está o plugin de status do rhythmbox
Editar: veja este encadeamento no rhythmbox e status do IM