Uma atualização do sistema ou atualização do Clementine pode corrigir o problema. Do terminal tente:
sudo apt-get update sudo apt-get upgrade clementine
É uma boa prática sair de aplicativos antes de desligar; Eu tentaria isso também. Em seguida, você pode tentar desligar do terminal (o que eu faço everytime com o Ubuntu Server 12.04):
sudo poweroff now
Adicione a opção -f para forçá-lo se isso não funcionar. Há também uma opção --verbose que ajudará a identificar o problema. Por fim, você pode matar o (s) processo (s).