this is almost certainly a dns issue. your router acts as a dns relay server to your isps and also for local machines.
the server, when it receives an ssh connection, will try and perform a reverse dns lookup on the ip it gets a connection from. this query will go to your router which if it hasn't got a dns entry for that ip will return name not found.
2 solutions to this problem.
get dns working properly on your network so you can ping machines by hostname. this will probably require some config on your router.
configure your servers so they don't carry out the rDNS lookup. looking through the man pages should help you with this
Quote:
I tried 'UseDNS no' in sshd_conf - but didn't fix.
|
did you restart sshd after this? The option may not be the same depending on version of sshd you have.