On the destination server, remove the known_hosts file:
rm ~/.ssh/known_hosts
Remove any relevant entries in your /etc/hosts.deny file:
/etc/hosts.deny: # DenyHosts: Fri Jun 25 16:10:25 2010 | sshd: xxx.xxx.xxx.xxx sshd: xxx.xxx.xxx.xxx
Also, try this in your /etc/hosts.allow file
/etc/hosts.allow: SSHD: ALL