Eu tenho uma resposta, mas ainda não sei por que isso foi um problema. Por favor, veja o post original para uma descrição detalhada do problema exato.
No final, em vez de nos conectarmos no painel "Rede" como de costume, digitei o comando:
nmcli d wifi connect YOUR_NETWORK password YOUR_NETWORK_PASSWORD iface wlan0
A linha de comando foi a única opção para mim. Eu estou realmente surpreso que ninguém sugeriu este simples passo, mas aqui está para a posteridade! Obrigado a todos que participaram e me indicaram onde procurar problemas.