Update: from the info I've gathered, this is most probably a problem with some Cisco IDS/DPI is running on the ethernet equipment. Workaround is available in the content below, I still don't know what's the real solution here (Cisco equipment config? update Cisco firmware?)
Starting with 5.7p1, ssh client on specific environments fails connecting to specific (usually old versioned) servers. I reproduced it on a particular network, while trying to connect using new ssh client (5.8p1, Ubuntu 11.04) to an old server (default SSH server on RedHat 5.4).
This issue is around for quite a while, but is very tricky to reproduce or understand. What bothered me most is that many people reported it to different forums, each posting only a few (different) pieces of the puzzle. So my motivation here is to try and summarize the relevant info from multiple places. I'll do my best to update this post when I hear something new.