É muito estranho, mas finalmente consegui que funcionasse.
Primeiro eu desinstalei o NetworkManager
sudo apt-get remove --purge network-manager-gnome network-manager
Então eu instalei o wicd, que foi capaz de se conectar à minha rede
sudo apt-get install wicd-gtk