Some users experienced problems with glest (and gae) in Ubuntu. I know how to fix it.
If glest/gae doesn't run at all, you might need dependencies to run glest/gae binaries. run this command:
sudo apt-get install bjam jam checkinstall auto-apt build-essential cvs subversion subversion-tools automake vim libsdl1.2-dev libxerces27 libxerces27-dev libopenal0a libopenal-dev libogg0 libogg-dev libvorbis0a libvorbis-dev
This installs dependencies and I added packages needed to compile glest/gae (this may be useful
. The simplest way to fix is to remove the screensaver. It is somewhere in System==>preferences I think.
To play with glest/gae, I hope you have the "restricted drivers" needed for your graphic card. You can install more recent drivers (for nvidia and ati) with envy if you want (uninstall the "restricted drivers" before, envy drivers are closed source too but more recent). enter this command :
in gnome (ubuntu)
sudo apt-get install envyng-core envyng-gtk
in kde (kubuntu)
sudo apt-get install envyng-core envyng-qt
Then envyng program can be found in applications menu , it can install drivers.