Can't restore from Time Machine server
Is the new 'replaced' client running on the same level of OS as your other clients?

I ran into the same error message when trying to restore a backup, and only got past it when I first upgraded the OS on the new hard drive to the same level as the prior hard drive was running when the most recent back up was made.  That is, I skipped restoring files to the computer until I completed initializing the new drive, then upgraded the OS, and finally went back and restored applications and documents.