OK, isso foi realmente desagradável porque há um ninho de dependência lá que simplesmente não vai embora com a rodada usual de limpeza do apt-get, apt-get -f install, etc. O único caminho em volta deste (Eu recriei seu problema em uma VM e testei) é apenas colocar um diretório ali para o apt se livrar de em primeiro lugar.
root@yourbox:/# mkdir -p /usr/share/postgresql/8.4/tsearch_data
root@yourbox:/# apt-get purge postgresql-8.4
root@yourbox:/# apt-get autoremove
Com um diretório vazio para o apt to remove, tanto a limpeza inicial do pacote pai quanto a remoção automática dos pacotes filhos foram concluídas sem erros na minha VM.