Primeiro, desinstale o pacote zeitgeist e permita que o gedit seja automaticamente desinstalado. Então:
sudo su
apt-get download gedit
apt-get download gedit-plugins
dpkg --force-all -i gedit_3.6.0-0ubuntu1_amd64.deb gedit-plugins_3.6.0-0ubuntu1_amd64.deb
Só fiz isso no Xubuntu 12.10 e parece funcionar bem no meu sistema. Note que o nome exato dos arquivos deb será diferente. Você deve desativar o plugin zeitgiest que ainda será instalado no gedit, já que presumivelmente ele não funcionará de qualquer maneira.
(nota: comando dpkg emprestado desta questão):
Como você pode instalar um pacote sem instalar alguns dependências?