Eu finalmente encontrei o problema, o wpa_supplicant não estava sendo executado.
Tente isto:
sudo systemctl start wpa_supplicant.service
Agora verifique novamente a lista de Wi-Fi:
nmcli dev wifi list
Conecte-se à rede assim:
nmcli --ask connection up <ssid>