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.
UPDATE: rpcbind-0.2.0-3 was just released, and it solves all the rpcbind issues.
UPDATE2: THE BUG WAS SOLVED! Alexander Wirt patched nfs-kernel-server: by removing the linkage of libtirpc, it now uses the previously method of IPv4 binding, thus not triggering the problem. When/if would rpcbind replace portmap - I don't know.
[ This article describes my analysis to a problem found in Debian Unstable(sid) ]
Since the end of December, a change in nfs-kernel-server package caused a change of behavior in some NFSv3 crucial services: rpc.statd, rpc.mountd. NFS is RPC-based, and as thus, it uses an RPC-to-UDP/TCP address translation service, aka port mapper. These services try to connect to port mapper when they need address translation, and since the recent change they first try to do it over IPv6.
portmap, the current widely-used rpc port mapper service, does not support IPv6. This causes these crucial services to die, and NFSv3 fails to start (actually, with default configuration it even prevents starting an NFSv4 server).