Eu sei que é tarde, mas gostaria de saber que tipo de VPN você está usando.
Eu tive esse problema com o Cisco Anyconnect VPN.
Não vendo o mesmo erro que você, mas o comando pareceria ser executado, mas a tabela de roteamento ainda seria a mesma.
Eu acredito que o Cisco AnyConnect bloqueia a tabela de roteamento de alguma forma, de modo que não possa ser modificado.
Se não for o Cisco AnyConnect, pode fazer algo semelhante. Eu não encontrei nenhuma documentação sobre isso, mas essa é a conclusão a que cheguei do meu teste.
Descobri que isso também parece se aplicar ao Windows.
Felicidades, Aaron