Problem is fixed. Using rsync -av fixes it.
Looks like there is some bug in the -r switch.

> I am using rsync over ssh (set RSYNC_RSH=ssh) to copy a bunch of files
> between 2 linux boxes [RH 8.0 client and RH 9.0 server]. Both ends are
> running rsync 2.5.6, after compiling from sources.
>
> I notice that rsync copies *all* the files even if nothing changes.
> The way I can tell is that the time stamp changes for all the files on
> the client side.
>
> The command I used was:
>
> export RSYNC_RSH=ssh
> rsync -rv root@colby:/var/tmp/rgy .
>
> -Shanker