問題点:
Tera Term 4.90 をデフォルト設定で使っていると、古い Solaris のサーバ(Solaris 9 だけ?)に以下のメッセージが出て接続出来ない。

unknown KEX algorithm: diffie-hellman-group1-sha1

とりあえずの解決法:
Tera Term の「設定」-「SSH」にある「優先する鍵交換アルゴリズムの順」で "diffie-hellman-group1-sha1" の優先順位を一つ(以上)上げる。

お勧めの解決法:
Solaris のサーバに最新の OpenSSH をインストールして使う。

……というバグを入れてしまいました。orz
変更履歴でいうと

鍵交換方式ですべての方式を有効にしている時に最後の方式が使われない問題を修正した。

という奴です。

このバグが入った背景ですが、ssh の通信経路の暗号化やホスト鍵としてより安全な新しい方式が出て来ているので、
それに合わせて鍵交換方式でも安全な方式を追加しようという動きがあり、Internet-Draftが書かれました。
Tera Term 4.90 ではこの Internet-Draft で追加された新しい方式に対応しました。

ssh の鍵交換では、利用する鍵交換方式の候補を , で繋げた文字列として送るのですが、新しい方式が増えた事でこの時に送る文字列も長くなります。
そして、対応している方式を全部有効にした場合の鍵交換方式のリストが長くなりすぎて、処理に利用しているバッファに収まらなくなってしまいました。
その為、一番後ろにある鍵交換方式名を途中で切り詰めて送ってしまい、サーバ側でその方式が正しく認識できず使われなくなりました。
この一番後ろになる鍵交換方式は優先度が一番低く設定した物になります。デフォルト設定では diffie-hellman-group1-sha1 が該当します。
そして、Solaris 9 で使われている SunSSH 1.0 では鍵交換方式としてこの diffie-hellman-group1-sha1 しか使えない為、鍵交換が行えなくなりました。

という事で、とりあえずの対処としては最初に挙げた「diffie-hellman-group1-sha1 の優先度を上げる」方法になります。
しかし、diffie-hellman-group1-sha1 は 1024 ビットの強度しかなくしかも SHA-1 を利用している為、今となってはかなり弱い方式です。
最新の OpenSSH ではデフォルトでは無効にされていますし、Tera Term でも将来のバージョンではデフォルトでは無効化する事を検討しています。
なので、このような安全では無い方式を使わずに、最新の OpenSSH を入れてそちらを利用する事をお勧めします。

2016/6/1追記:
実は他にも Juniper の SSG や Cisco の一部の(古い)機器などでも問題が出たらしいです。
Tera Term を最新の 4.91 にバージョンアップすればデフォルト設定でも接続できるようになります。

Cisco の機器に関しては一部の機器が diffie-hellman-group-exchange-* (GEX) で大きいグループサイズを受け付けないという問題が有って対処を入れたりした事から
普通は GEX に対応しているもんだと思っていましたが、diffie-hellman-group1-sha1 のみの機器(IOSのバージョン?)も有ったのかと意外でした。

こうなると diffie-hellman-group1-sha1 の無効化は簡単に出来ないなあ。