General :: Install SSH Server On Ubuntu?

I just installed Ubuntu 9.10 on a machine here. Tried to SSH to it and failed. Tried to "ssh localhost" from the machine itself and that failed. Did a quick google search and found out that an SSH server is not installed by default.

But how do I install it?

I tried the following, which failed:

Code:
sudo apt-get install openssh-server
Reading package lists... Done
Building dependency tree
Reading state information... Done

[Code]....