Do pacote deb do Terminator:
Depends: python (>= 2.5), python-support (>= 0.90.0), python-vte, python-**gobject**, python-**gtk2** (>= 2.14.0), gconf2, libgtk2.0-bin, hicolor-icon-theme
Portanto, você não poderá instalá-lo sem dependências, a menos que você a) cancele as dependências, ou b) seu sistema esteja corrompido. Tente o seguinte:
$ python
Python 2.7.6 (default, Jun 22 2015, 18:00:18)
[GCC 4.8.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import gobject
>>> import gtk
>>> import pango
>>>
Isso nos dirá o que está faltando, porque um deles falhará para você. Então, podemos descobrir por que está faltando e como instalá-lo.