Sorry,
I am not sure as I was really trying to get connected at the time so

I don't have a definite answer.

I have Redhat 6.1 and another machine is redhat 6.2
Both local servers refused connect from my OSX machine
all machines are running the same version of ssh
and
[Linux xxx]$ ssh -V
OpenSSH_2.9p1, SSH protocols 1.5/2.0, OpenSSL 0x0090581f

[OSX:/etc] xxx# ssh -V
OpenSSH_2.9p1, SSH protocols 1.5/2.0, OpenSSL 0x0090581f

I am not certain of the version which 10.04 introduced as the updater has checking which will prevent it from stomping on a higher version.

When I noticed the problem first I looked manually at the config files and determined that they were changed.

Then, I opened SSH config from gideon software and reset my settings and restarted the server.
--This did not help.
Frustrated, I returned to my Openssh source folder and typed "make install".

--Still it didn't work...though, this method does not regenerate keys or rewrite the configs.

I regenerated the keys manually.

It started working.

Seems that the trick is to regenerate the keys. !?!?!?!?!