Apenas encontrei este post antes, mas encontrei uma solução mais fácil para o Ubuntu 12.10.
Então, para compartilhar para qualquer pessoa que esteja procurando ...
O Ubuntu armazena os compartilhamentos de rede como uma pasta em /run/user/<user-name>/gvfs/<share-name>
No Clementine, basta adicionar essa pasta de compartilhamento. Economiza muito tempo.
Em 12.04, acho que é /home/<user-name>/.gvfs/<share-name>
, mas não tenho certeza se Clementine verá pastas ocultas que valem uma chance.