Comparing your setup with my notes, I noticed that I also do the following on the *server*:
# sudo -u <backup-user> ssh <client> And then abort after accepting the host key. Did you do this as well? Otherwise try to run "amrecover -o debug_auth=1" on the client and check the log files. You should now see the SSH call being performed. HTH, Markus