apt-cache search gtkspell encontra o pacote python-gtkspellcheck , que soa exatamente como você deseja.
Você também pode encontrá-lo na lista de pacotes recomendados de zim :
$ apt-cache show zim | grep '^Recommends:'
Recommends: python-gtkspell
Você pode exibir e instalar os pacotes recomendados através do Synaptic através do menu de contexto ou através do Apt (com a opção --install-recommends no caso de você ter desativado a configuração padrão APT::Install-Recommends ):
sudo apt-get install --install-recommends zim