Having upgraded openssh I am now getting a prompt window with:

"The host key sent by the server is different from
the host key stored in the host key database for
IP address (#.#.#.#.# port 51. This may mean
that a hostile party has "hijacked" your connection
and you are not connected to the server you specified."

I've read that to stop this message I've to delete old client keys(done this) and the offending line in /root/ssh/known_hosts.(done this)

I still get the error for both servers that I've upgraded - what is it that I am doing wrong?

The upgrade file was found at http://pkg.nl.cobalt.com/

I think that:

since you upgraded your SSH installation on your server it is returning a different key. Depending on the SSH client you use on your local PC, you might have to clear the clients cache or just accept the new key/certificate from your server to get rid of the message. Defenitely make sure that the IP address reported in the message is the one from your server!

Cheers
Mark

I suppose that all clients that use ssh will have to regenerate their personal keys as well?

Yes, I am pretty certain that your clients using SSH will have to do so.

Cheers
Mark