Mike,

First reinitialize the "known_hosts" file by the following from your ssh client box:

cd ~/.ssh
rm known_hosts
ssh <username>@<IP address of ssh host box>
   - Ubuntu will ask you for confirmation of your request to setup a key on the server -
Type yes or 'y' which ever it asks for
type in password when prompted
   - you should now have prompt for <username>@<ip address of ssh host box>:$

This should rewrite the known_hosts file in your user directory on the client box

At this point you should be able to ssh into your host by using the <username>@ip address of host box>

If you can't than perhaps you setup up public keys for authentication. If you have public keys setup than you should see 2 files named "id_rsa" and "id_rsa.pub" on your ssh client machine in a directory named "/home/<username>/.ssh". id_rsa is your private key that needs to remain here.  The id_rsa.pub is the public key that needs to be copied to your ssh server.  If you see the id_rsa.pub file and you still know your passphrase that you setup (if you set one up) than it is a matter of appending id_rsa.pub into a file called "authorized_keys" located in ~/.ssh on the host computer.  If you only have the single client connected to the host than you can rename the authorized_keys file on your host and append id_rsa.pub to a new version. NOTE if you do not see the id_rsa.pub file and only have the id_rsa file than you will need to generate a new set of public keys (see Method 2). 


Method 1
If you have been able to establish simple ssh between the 2 boxes, from the client computer (where id_rsa.pub is found) it might be as simple as typing the following:

ssh <username>@host ip address> "cat >> ~/.ssh/authorized_keys" < ~/.ssh/id_rsa.pub

or after establishing an ssh connection typing the following:

"cat >> ~/.ssh/authorized_keys" < ~/.ssh/id_rsa.pub

If ssh is not working you will need to get the id_rsa.pub onto the host computer and append it from there.  Logon to host computer as user to be authenticated and copy the file using "scp" command and place it in the ~/.ssh directory. 

Method 2 (New keys)

To generate new keys type the following from the client box (do not do this using sudo or as root but as your own username):

ssh-keygen -t rsa
  - Ubuntu will prompt you for the location to place the key pairs just pick the default
  - You will be prompted for a passphrase
  -  You will be asked for passphrase confirmation
 
 Then copy the id-rsa.pub file to the host computer by Method 1.

--
James