Es raro, yo acabo de hacer una instalación limpia de Ubuntu, he pasado de karmic a Lucid, he configurado mi tarjeta de red y ningún problema (yo lo tengo cableado), aunque el router lo tengo en modo cliente.
Hay una alternativa al network-manager, se llama Wicd. Pruebalo y comenta.
Al instalar Wicd el network-manager desaparece!!!