Rsh/rsync problems

[ebzzry]

With no visible reason why, rsh and rsync+rsh stopped working for me.
When I run rsync, I get this message:

rcmd: socket: Can't assign requested address
rsync: connection unexpectedly closed (0 bytes received so far) [sender]
rsync error: error in rsync protocol data stream (code 12) at io.c(468) [sender=2.6.8]
rsync exited with error code 12

I checked /var/log/messages and I saw repeated lines that looked like the following:

rshd[68618]: can't get stderr port: Can't assign requested address

What could be causing it? Any hints guys?