Hola lrs,
Entiendo que en realidad tienes un Ubuntu 8, 9 ó 10.
Con windows mobile y Ubuntu 9, hacía falta configurar cosas en Ubuntu para que funcionara. Con Android no lo he mirado, la verdad, pero seguramente usen técnicas parecidas para tehtering frente al sistema operativo. Te sugeriría mirar en foros internacionales si no encuentras nada por aquí.
Qué te pregunte por WEP es muy raro, porque WEP es protocolo de encriptación para wifi y no se usa en tethering.
Si sólo vas a hacer tethering de vez en cuando y poco rato, igual te interesa hacer tehtering por wifi o bluetooth y así te quitas de problema de drivers de Ubuntu, en caso de que finalmente necesitara. El único problema es que con tethering por wifi la batería de Legend te durará 40 minutos ó 1 hora máximo. Puedes hacer Tethering por wifi con el cable USB conectado para alimentar Legend, per en mi caso (con mi rom, etc...) me consume un poco más de lo que carga, con lo que al final tendrás tiempo limitado de navegación según la duración de la batería.