A capacidade de definir uma nova conexão na linha de comando com nmcli dev wifi con … foi adicionada no NetworkManager 0.9.6. (Se você estiver usando o Ubuntu, isso significa release 12.10 ou superior.) Em versões anteriores, novas conexões só podem ser definidas através da GUI ou editando arquivos de configuração manualmente (em /etc/NetworkManager/system-connections ou em ~/.gconf ). Você pode ativar uma conexão existente com nmcli con up .
Se você não tiver uma GUI para definir conexões, poderá tentar o wicd em vez do NetworkManager.