I get a traceback with the python you show above, but the system says that python2.5-gnome is installed. I've uninstalled and installed python2.5-runtime a number of times with no change in the behavior.
apt-get purge python2.5-gnome apt-get install python2.5-gnome