pasos:
1.- Te descargas el wicd (de su pagina, la version estable), abres una consola y escribe aptitude remove networkmanager, a continuacion siguiendo en consola te vas al directorio donde tengas el instalador (formato .deb, si no esta en su pagina, busca en los repos de lenny) y a continuacion escribe dpkg -i nombrearchivo y te lo instalara, ahora ya tendras un gestor mejor (aunque a mi no es que me guste tampoco porque de vez en cuando hace alguna cosa rara).
2.- Te conectas normal
3.- si alguna vez tienes problemas con algo de linux dpkg-reconfigure nombreprograma y cuando lo haya echo intenta arrancarlo.
El que desaparezca algo en ubuntu no me sorprende, metele debian, podrias intentarlo ejecutar desde consola haber si se abre
un saludo!!