The problem sounds like a server-side bug. When the client sends the list of ciphers the openssh server probably expects to be able to read the list in a single system call.
If the list of supported ciphers is longer than can be transmitted in one packet, the server may get fewer bytes in the first call than it expected. The correct behavior on the server would be to perform another call to get the rest of the bytes. But from the problem description it appears, the server instead closes the connection when it did not get the full list of ciphers at once. When the next packet from the client arrives, the server will send a connection reset to the client.
Configuring the client to use a shorter list of ciphers would then work around the bug. The openssh client will look for the list of ciphers in the following places:
- On the command line using either -c cipher_spec or -o Ciphers=cipher_spec
- In ~/.ssh/config by specifying Ciphers cipher_spec in the relevant host section or before the first host.
- In /etc/ssh/ssh_config using the same format as ~/.ssh/config
- A default list built into the client at compile time.
The two configuration files are respectively per-user and system-wide settings. Using
Ciphers aes128-ctr,aes192-ctr,aes256-ctr,arcfour256,arcfour128,aes128-cbc,3des-cbc like Eric suggested should work fine.