When launched from terminal:
---:~$ gdevilspie
pyGTK is not correctly installed, exiting.
Installed in 11.10 Using Ubuntu Software Center...

When launched from terminal:
---:~$ gdevilspie
pyGTK is not correctly installed, exiting.
Installed in 11.10 Using Ubuntu Software Center...

This bug report http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=628492
suggests python-glade2 is the missing dependency.
sudo apt-get install python-glade2
If that fixes the problem, you may wish to append your bug report on launchpad ;)