При запуске из терминала:
---:~$ gdevilspie
pyGTK is not correctly installed, exiting.
Установлено в 11.10 Использование программного центра Ubuntu ...
Этот отчет об ошибках http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=628492
предлагает python-glade2
недостающая зависимость.
sudo apt-get install python-glade2
Если это решает проблему, можно хотеть добавить отчет об ошибках на панели запуска ;)