Não tenho uma receita para isso, primeiro que raramento desinstalo um aplicativo, segundo que de tanto "fuçar" eu acabo sabendo qual arquivo é de que aplicativo (.mozilla para o firefox, .purple pro pidgin e etc) e ai eu simplesmente removo pelo terminal (usando o comando rm), ou através do nautilus.