Acabei de ter o mesmo problema e a resposta da Plant Maven estava correta.
Em vez de excluir os arquivos de configuração em /etc/NetworkManager/system-connections/
, movi-os para outra pasta, para poder comparar.
A única diferença entre o arquivo de configuração antigo e o novo é em uma conexão VPN que acabei de recriar do zero e é o UUID.
Nenhuma ideia do motivo pelo qual o arquivo antigo não funcionaria. Eu suspeito que seja algo relacionado ao chaveiro.