.. posted the complete output of the commands

On the debian server, login as user and type
note the . before ssh
Then try again

> rm .ssh/known_hosts
rm: cannot remove `.ssh/known_hosts': No such file or directory

You are doing all this as the user, not as root.

How did you installed ssh?
as root

..the synaptic package manager to install it.

try

> apt-get install ssh
Reading package lists...
Building dependency tree...
Reading state information...
The following packages were automatically installed and are no longer required:
libgsf-gnome-1-114 libx264-60 libenca0
Use 'apt-get autoremove' to remove them.
The following NEW packages will be installed
ssh
0 upgraded, 1 newly installed, 0 to remove and 0 not upgraded.
Need to get 1202B of archives.
After this operation, 45.1kB of additional disk space will be used.
Get: 1 http://debian.zetnet.co.uk lenny/main ssh 1:5.1p1-5 [1202B]
debconf: unable to initialize frontend: Dialog
debconf: (TERM is not set, so the dialog frontend is not usable.)
debconf: falling back to frontend: Readline
debconf: unable to initialize frontend: Readline
debconf: (This frontend requires a controlling tty.)
debconf: falling back to frontend: Teletype
dpkg-preconfigure: unable to re-open stdin:
Fetched 1202B in 1s (1075B/s)
Selecting previously deselected package ssh.
(Reading database ... 155549 files and directories currently installed.)
Unpacking ssh (from .../ssh_1%3a5.1p1-5_all.deb) ...
Setting up ssh (1:5.1p1-5) ...

try again to connect
ssh 127.0.0.1

> ssh 127.0.0.1
Host key verification failed.

are you sure there is no .ssh directory in your home directory?
try
If there isn't, I would suggest to use synaptic to reinstall
ssh, ssh-server
Seems to me it isn't correct, or fully installed.
It should work out of the box.

..enough for 1 day )

> tail -1 $HOME/.ssh/known_hosts
tail: cannot open `/root/.ssh/known_hosts' for reading: No such file or directory

I'll try the package manager again tomorrow night.

Thanks for your help.

You need to be user, not root.
also, you need to ssh as user, not root

first of all we should consider a few things before we are able to ssh when using openssh in Linux, i am using CentOS 5.2 and using openssh 5.1

• first thing is do we have openssh fully installed i.e openssh 5.1 rpm and openssh-server rpm must be installed.

• the ssh daemon must be in running state, to check it type
  
  Code:

  $ /sbin/service sshd status

  if it is not running then type
  
  Code:

  $ /sbin/service sshd start

• the firewall(iptables) must have a rule to allow port 22 access which is the default port for ssh, to check that type

• the selinux should be disabled as in my case, i often have problems when selinux is enabled, to disable selinux, open the file

and change the line "SELINUX=enforcing" to "SELINUX=disabled"
Now i hope you will be able to ssh to your machine.

@saifkhan123
Since telnet 127.0.0.1 22 works, and the error for ssh 127.0.0.1 is
The deamon is running, but here is a problem with the Host key verification

The OP needs to remove .ssh//known_hosts as the user who connects to ssh (not the root user), in order to resolve the problem.

Agains many thanks for your help, Repo you said:

Em, er um.... what's an OP ?


Just to continue from where we left off last night...I used apt-get remove ssh as root then tried to install it as user (guess that's wrong too? )

ludo1960@debian:~$ apt-get install ssh
E: Could not open lock file /var/lib/dpkg/lock - open (13 Permission denied)
E: Unable to lock the administration directory (/var/lib/dpkg/), are you root?

Now if only I knew what OP meant and which file to remove before jumping the gun again, I guess user ludo1960 needs a key too.