Ah, eu descobri que a senha do "Shared Secret" "Machine Authentication" era inválida. Eu a redefino e agora ela se conecta corretamente em todas as máquinas.
(Pena que a mensagem de erro estava totalmente incorreta. Espero que alguém encontre isso antes de passar horas resolvendo o problema ...: ^ /)