Obrigado a quem respondeu!
Eu tive uma onda cerebral rápida e tentei outra coisa:
Eu fui ao meu roteador mais externo (nosso modem CentryLink) e mudei a porta SSH para 22222, depois fui para o outro roteador (Netgear AP) e configurei a porta externa para 22222. O que provavelmente estava acontecendo era que o Pi era tentando SSH no modem, em vez do servidor.
Feito isso, tudo funciona!