Ubuntu 9.04 upgrade to 9.10 now ssh not working

I just upgraded a (Linode VM) Ubuntu 9.04 to 9.10 using do-release-upgrade (as root). Now, ssh is not working.

At first, I was just getting "Connection timed out". So, I went to the Linode website and used their "lish ajax console". Not sure how this is different than ssh as it uses the same root password (which still works). There, I found that the file system was mounted as read-only. I fixed this by doing mount -t ext2 -o rw,remount /dev/hda6 /, but still no ssh connection. I then (still using the "lish ajax console" on the Linode website) used the command dhclient eth0, and now I am getting "Connection refused" instead of "Connection timed out", which feels a bit like progress but not much.

So, I can tell that the upgrade from 9.04 to 9.10 has not gone especially well. I can still see all my files using Linode's "lish ajax console", but I don't know how to get ssh to work, and unsurprisingly the websites on this server are not accessible anymore either.

Since the "lish ajax console" uses the same root password, I'm guessing that is still working, and all of the files I've looked for so far are there so not all is lost. But, I must need to do something else to get ssh working again. Any ideas?

p.s. Ok, thanks for hints, here's the results so far:

/etc/init.d/ssh status
could not access PID file for sshd
/etc/init.d/ssh start
Starting OpenBSD Secure Shell server sshd
/etc/init.d/ssh status
sshd is running

That sounded good, but then when I tried to puTTy in I got:

Server refused to allocate pty
stdin: is not a tty

I poked around the internet for a bit and found out to try this:

/sbin/MAKEDEV pty
/sbin/MAKEDEV tty

But, no improvement.

ifconfig eth0

This gave confirmation that the IP address ("inet addr:") was what I expected.

iptables -I INPUT -p tcp --dport -j ACCEPT
bash: iptables: command not found

I found it kind of surprising that it had not heard of iptables, but what do I know. All I could find in the auth.log was this, not from now but from several hours ago.

root@localhost:/var/log# tail -f /var/log/auth.log                                                  
Apr 16 15:05:50 li9-111 sshd[10704]: pam_unix(sshd:auth): authentication failure; logname= uid=0 eui
d=0 tty=ssh ruser= rhost=60.10.58.156  user=root                                                    
Apr 16 15:05:52 li9-111 sshd[10704]: Failed password for root from 60.10.58.156 port 32776 ssh2     
Apr 16 15:05:58 li9-111 sshd[10706]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=60.10.58.156 user=root                                                    
Apr 16 15:06:00 li9-111 sshd[10706]: Failed password for root from 60.10.58.156 port 33096 ssh2     
Apr 16 15:06:03 li9-111 sshd[10708]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=60.10.58.156  user=root                                                    
Apr 16 15:06:05 li9-111 sshd[10708]: Failed password for root from 60.10.58.156 port 33588 ssh2     
Apr 16 15:06:11 li9-111 sshd[10710]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=60.10.58.156  user=root                                                    
Apr 16 15:06:14 li9-111 sshd[10710]: Failed password for root from 60.10.58.156 port 33927 ssh2     
Apr 16 15:06:16 li9-111 sshd[10712]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=60.10.58.156  user=root                                                    
Apr 16 15:06:18 li9-111 sshd[10712]: Failed password for root from 60.10.58.156 port 34404 ssh2 

In the syslog all I could find was this:

root@localhost:/var/log# tail -f /var/log/syslog

Apr 16 15:05:19 li9-111 mysqld: Active alarms: 0                                                  
Apr 16 15:05:19 li9-111 mysqld: Max used alarms: 1                                                  
Apr 16 15:05:19 li9-111 mysqld: Next alarm time: 0                                                  
Apr 16 15:05:19 li9-111 mysqld:                                                                     
Apr 16 15:05:19 li9-111 mysqld: Begin safemalloc memory dump:                                       
Apr 16 15:05:19 li9-111 mysqld:                                                                     
Apr 16 15:05:19 li9-111 mysqld: End safemalloc memory dump.                                         
Apr 16 15:05:48 li9-111 dhclient: DHCPREQUEST of 67.18.176.111 on eth0 to 72.14.180.19 port 67      
Apr 16 15:05:48 li9-111 dhclient: DHCPACK of 67.18.176.111 from 72.14.180.19                        
Apr 16 15:05:48 li9-111 dhclient: bound to 67.18.176.111 -- renewal in 35362 seconds.  

Lastly,

root@localhost:/var/log# netstat -ntlp                                                              
Active Internet connections (only servers)                                                          
Proto Recv-Q Send-Q Local Address           Foreign Address         State       PID/Program name    
tcp        0      0 0.0.0.0:22              0.0.0.0:*               LISTEN      891/sshd            
tcp6       0      0 :::22                   :::*                    LISTEN      891/sshd    

Thanks much for all the help so far, any further advice is greatly appreciated.
Last Note: just in case something above wouldn't take affect until reboot, I tried that and the result was a step backwards (no response to attempt to ssh). So, I went back to the top and tried:

root@localhost:~# /etc/init.d/ssh status                                                            
 * could not access PID file for sshd                                                               
root@localhost:~# /etc/init.d/ssh start                                                             
 * Starting OpenBSD Secure Shell server sshd                             [ OK ]                     
root@localhost:~# /etc/init.d/ssh status                                                            
 * could not access PID file for sshd            

Which seems like maybe a step backwards. Anyway, any help or advice is appreciated.