Este relatório de bug link
sugere que python-glade2
é a dependência ausente.
sudo apt-get install python-glade2
Se isso resolver o problema, você poderá anexar seu relatório de erros no launchpad;)
Quando iniciado a partir do terminal:
---:~$ gdevilspie
pyGTK is not correctly installed, exiting.
Instalado no 11.10 Usando o Ubuntu Software Center ...