Ah, I figured it out --- the "Shared Secret" "Machine Authentication" password was invalid. I reset it, and now it connects properly on all machines.
(Too bad the error message was totally incorrect. Hopefully someone else will find this before spending hours troubleshooting it... :^/ )