Restore from SSH fails with Host key verification failed.

Hi folks, this is killing me, I cant troubleshoot it, and cant seem to find where the problem is. Systems inovlved:

Cloud master, Host, backupnas, VM

I am trying to restore a backup from nightly backups to SSH. When I do I get the following:


Restoring 1 systems from /c/backup/virtual/2013-03-19 on SSH server XXX.108.146.33 as root ..

Finding systems to restore ..
.. found 1 systems
Working out backup sources ..
.. found 1 usable sources

Shutting down sparcs-tng prior to restore ..
.. done

Restoring sparcs-tng from /c/backup/virtual/2013-03-19/sparcs-tng.gz on SSH server XXX.108.146.33 as root ..
Restoring copies of disks for sparcs-tng via SSH from XXX.108.146.33 ..
.. restore failed : Failed to restore copy of LVM disk /dev/lv_storage/lv_sparcs_tng : Host key verification failed.
Starting up sparcs-tng after restore ..

I have searched all the machines involved, to make sure that keys are there and working, I have SSHed back and forth from all the machines involved as both root and the username used by the cloudmaster. without passwords but cannot figure out why its failing. I have had to manually restore these backups (painful), can anyone suggest a place to try? I have been monitoring the auth.log on all hosts and the webmin.log on the cloudmin master but cannot see whaere the problem is. Any help is greatly appreciated.