O que faz ele funcionar são os drivers das placas wireless e o pacote wpa_supplicant. Drivers, você tem; o pacote wpa_supplicant, também. Então, sabendo como configurar, tem que funcionar também.
Uma alternativa seria você instalar o wicd ("apt-get install wicd") no lugar do NetworkManager, e ver se com ele vc consegue configurar a conexão satisfatoriamente.
Muita gente diz que o wicd funciona melhor que o NM, mas ele tem a desvantagem de só trabalhar com cabo e wireless, não consegue fazer 3G.