Disculpa que insista, pero ¿lo probaste? porque busqué el problema y el primer resultado dice basicamente lo mismo que te escribí antes (
http://bugs.python.org/issue2410)
razpeitia, ese problema parece ser específico de Ubuntu, según el reporte del bug. Además parece culpa de los programadores de labyrinth (lo que sea que eso sea), si el paquete está instalado correctamente, ¿por qué modificar el sys.path de esa forma? Parece algo tonto.
Dudo que smtplib tenga el mismo error.