Ah, then your problem is the other way round from mine -- I use the Windows box as the client side, so this is fine.

How are you running sshd? As a daemon, or through inetd (I assume Cygwin's got one), or something else?

One thing you can try is (from the Linux box):

rsync -e ssh --rsync-path='nice rsync' the-rest-of-the-options

The '--rsync-path' switch tells it which application to run on the other end -- it's supposed to be used if your binary is not in $PATH.