Хорошо, похоже, проблема заключалась в том, что я пытался подключиться по SSh к эластичным IP-тискам, используя DNS-имя рассматриваемого AMI. Не знаю, почему это работало раньше, а не сейчас, но вот оно.
Можете ли вы установить Telnet на порт 22 на этом сервере? Не догадываюсь, но попробовать стоит. Если нет, у вас такой же внешний IP-адрес, как и у других серверов? Если вы это сделаете, это, вероятно, где-то локальный брандмауэр. Если вы этого не сделаете, я предполагаю, что вы случайно заблокировали себя на внешнем сервере. Проверьте /etc/hosts.deny на предмет вашего IP-адреса и, возможно, iptables на нем.