Eu não sei por que Clementine não encontra músicas no começo, mas eu posso transferir músicas de qualquer maneira:
Clique com o botão direito do mouse em uma faixa e selecione "Copiar para o dispositivo ...", pode demorar um pouco, mas funciona, pelo menos para mim (você verá um indicador de progresso dizendo "Organizando arquivos ... "sob controles de reprodução).
Por sinal, meu dispositivo é o Nexus 4 com Android KitKat e estou usando o Clementine 1.2.3.