Então, depois de MUITO mais trabalho nisso ... eu descobri que eu realmente poderia entrar na máquina (embora não através do SSH). Quando desliguei o openvpn, consegui voltar ao SSH normalmente. Suspeita confirmada.
Então, a pergunta se tornou: como faço para o SSH em um cliente OpenVPN?
Para qualquer outra pessoa que tenha o problema, também estou colocando a solução aqui:
ip rule add from x.x.x.x table 128
ip route add table 128 to y.y.y.y/y dev ethX
ip route add table 128 default via z.z.z.z
Where x.x.x.x is your public IP, y.y.y.y/y should be the subnet of your public IP address, ethX should be your public Ethernet interface, and z.z.z.z should be the default gateway.