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.

Try it with AFP ON. Although AFP is deprecated, it has been shown to be more reliable with Time Machine over networks than SMB.

Is your 'replaced client' the exact same machine name and user as before? if not, you may not have permission to access. The alternative is to take the new client an 'restore from Time Machine' when booted from the recovery partition. This will, of course, wipe the existing data from the hd.