Strange SSH/rsync issue

Having ordered a new server, I finally got it yesterday. I thought I’d set it up to act as secondary nameserver, backup mysql and general user-data backup but when I started backing up some of the data from the old server (via rsync over ssh) I found that every few minutes the rsync would die with the error:
Corrupted MAC on input.
This error both showed up in the shell running rsync and also in /var/log/secure on the new server as
Sep 11 16:45:11 server sshd[8254]: Disconnecting: Corrupted MAC on input.