Para encontrar o nome do pacote para um determinado arquivo, use:
dpkg --search /usr/bin/couchdb
no meu sistema, isso retorna couchdb-bin
, então você deve fazer:
sudo apt-get --purge remove couchdb-bin
Repita quantas vezes forem necessárias.