Rasum 様へ。

他のパッケージはインストールできますか？

以前に dpkg などで無理なパッケージのインストールしたり、
パッケージインストール中に電源を落としたことはありませんか？
これに心当たりがあれば、以下のコマンドを実行してみてはいかがでしょうか？

$ sudo apt-get -f install

Rasum 様へ。

wajig というコマンドは使ったことがないのですが、パッケージのバージョンを
固定するコマンドですよね？これが原因ではないでしょうか？
wajig が邪魔をして必要なパッケージをインストールできないか、
依存関係にあるパッケージをアップグレードできないか…。

おそらく、何らかの理由でバージョンを上げたくないのだと思いますが、
一度、バージョンの固定を解除してみてはいかがでしょうか？
openssh-server インストール後、wajig でバージョンを固定していた
パッケージ群をダウングレードさせ、再び固定すればよい気がするのですが…。

直前の投稿への補足です。
-s を付けたapt-get installの後、-f でもやっていますが同じ結果です。

# apt-get -f install openssh-server
パッケージリストを読み込んでいます... 完了
依存関係ツリーを作成しています               
状態情報を読み取っています... 完了
インストールすることができないパッケージがありました。おそらく、あり得
ない状況を要求したか、(不安定版ディストリビューションを使用しているの
であれば) 必要なパッケージがまだ作成されていなかったり Incoming から移
動されていないことが考えられます。
以下の情報がこの問題を解決するために役立つかもしれません:

以下のパッケージには満たせない依存関係があります:
openssh-server : 依存: openssh-client (= 1:5.9p1-5ubuntu1) しかし、1:5.9p1-5ubuntu1.1 はインストールされようとしています
                  推奨: ssh-import-id しかし、インストールされようとしていません
E: 問題を解決することができません。壊れた変更禁止パッケージがあります。

（"# apt-get install openssh-server"でも同じでした）

2014 Jan. 05.

katsu07様、ありがとうございます。
/etc/apt/sources.listに
deb http://jp.archive.ubuntu.com/ubuntu/ precise-updates main restricted
deb-src http://jp.archive.ubuntu.com/ubuntu/ precise-updates main restricted
を追記しました。
# apt-get update
# apt-get upgrade
では何もインストールされませんでしたが、
# apt-get install openssh-server
で
取得:1 http://jp.archive.ubuntu.com/ubuntu/ precise-updates/main openssh-server i386 1:5.9p1-5ubuntu1.1 [343 kB]
取得:2 http://jp.archive.ubuntu.com/ubuntu/ precise/main ssh-import-id all 2.10-0ubuntu1 [6,598 B]
とインストールできました。

今まで気づかなかったですが、CDインストールのデフォルトではupdatesがないのは何か意味があるのでしょうか。
2014 Jan. 06.

突然すみません。
#aptitude install openssh-server
で提示されるいくつかの選択肢から一つを選べば解決されると思います。
出来なければ、
#aptitude update
#aptitude safe-upgrade
#aptitude safe-upgrade
#aptitude safe-upgrade
を順番に実行します。
エラーが出るかもしれませんが、無視します。
最後の#aptitude safe-upgradeで、アップグレートするパッケージがないと出たら、
最初の#aptitude install openssh-serverを実行してください。