Dê uma olhada em / etc / bash_completion. Eu imagino que seu problema está na função _cd (). Realmente não posso ajudar nos detalhes, a menos que você publique o seu.
No meu caso (LMDE), a conclusão funciona como você descreve. Você pode dar uma olhada no meu /a / default / bash_completion aqui . Tente compará-lo com o seu, ou apenas substituindo o seu com este.