$ sudo apt-get install openssh-server
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 openssh-server : Depends: openssh-client (= 1:5.9p1-5ubuntu1)
                  Recommends: xauth but it is not going to be installed
                  Recommends: ssh-import-id but it is not going to be installed
E: Unable to correct problems, you have held broken packages. 

有人说要卸载掉 openssh-client , 但是 openssh-client 被很多包依赖, 很多的 xserver 的包都依赖它, 这该怎么办好?

用 aptitude 仍然不行:

$ sudo aptitude install openssh-server
The following NEW packages will be installed:
  gcc-4.6-base:i386{a} libbsd0:i386{a} libc-bin:i386{ab} libc6:i386{ab} libcomerr2:i386{a} libedit2:i386{a} 
  libgcc1:i386{a} libgssapi-krb5-2:i386{ab} libk5crypto3:i386{ab} libkeyutils1:i386{a} libkrb5-3:i386{ab} 
  libkrb5support0:i386{ab} libselinux1:i386{a} libssl1.0.0:i386{ab} libtinfo5:i386{a} libx11-6:i386{ab} libxau6:i386{a} 
  libxcb1:i386{ab} libxdmcp6:i386{a} libxext6:i386{ab} libxmuu1:i386{a} openssh-client:i386{ab} openssh-server 
  ssh-import-id{a} xauth:i386{ab} zlib1g:i386{a} 
0 packages upgraded, 26 newly installed, 0 to remove and 0 not upgraded.
Need to get 9,157 kB of archives. After unpacking 24.0 MB will be used.
The following packages have unmet dependencies:
 libkrb5-3 : Breaks: libkrb5-3:i386 (!= 1.10+dfsg~beta1-2ubuntu0.3) but 1.10+dfsg~beta1-2 is to be installed.
 libkrb5-3:i386 : Breaks: libkrb5-3 (!= 1.10+dfsg~beta1-2) but 1.10+dfsg~beta1-2ubuntu0.3 is installed.
 libk5crypto3 : Breaks: libk5crypto3:i386 (!= 1.10+dfsg~beta1-2ubuntu0.3) but 1.10+dfsg~beta1-2 is to be installed.
 libk5crypto3:i386 : Breaks: libk5crypto3 (!= 1.10+dfsg~beta1-2) but 1.10+dfsg~beta1-2ubuntu0.3 is installed.
 libc-bin : Conflicts: libc-bin:i386 but 2.15-0ubuntu10 is to be installed.
 libc-bin:i386 : Conflicts: libc-bin but 2.15-0ubuntu10.4 is installed.
 xauth : Conflicts: xauth:i386 but 1:1.0.6-1 is to be installed.
 xauth:i386 : Conflicts: xauth but 1:1.0.6-1 is installed.
 libxcb1 : Breaks: libxcb1:i386 (!= 1.8.1-1ubuntu0.2) but 1.8.1-1 is to be installed.
 libxcb1:i386 : Breaks: libxcb1 (!= 1.8.1-1) but 1.8.1-1ubuntu0.2 is installed.
 libkrb5support0 : Breaks: libkrb5support0:i386 (!= 1.10+dfsg~beta1-2ubuntu0.3) but 1.10+dfsg~beta1-2 is to be installed.
 libkrb5support0:i386 : Breaks: libkrb5support0 (!= 1.10+dfsg~beta1-2) but 1.10+dfsg~beta1-2ubuntu0.3 is installed.
 openssh-client : Conflicts: openssh-client:i386 but 1:5.9p1-5ubuntu1 is to be installed.
 openssh-client:i386 : Conflicts: openssh-client but 1:5.9p1-5ubuntu1.1 is installed.
 libx11-6 : Breaks: libx11-6:i386 (!= 2:1.4.99.1-0ubuntu2.1) but 2:1.4.99.1-0ubuntu2 is to be installed.
 libx11-6:i386 : Breaks: libx11-6 (!= 2:1.4.99.1-0ubuntu2) but 2:1.4.99.1-0ubuntu2.1 is installed.
 libgssapi-krb5-2 : Breaks: libgssapi-krb5-2:i386 (!= 1.10+dfsg~beta1-2ubuntu0.3) but 1.10+dfsg~beta1-2 is to be installed.
 libgssapi-krb5-2:i386 : Breaks: libgssapi-krb5-2 (!= 1.10+dfsg~beta1-2) but 1.10+dfsg~beta1-2ubuntu0.3 is installed.
 libc6 : Breaks: libc6:i386 (!= 2.15-0ubuntu10.4) but 2.15-0ubuntu10 is to be installed.
 libc6:i386 : Breaks: libc6 (!= 2.15-0ubuntu10) but 2.15-0ubuntu10.4 is installed.
 libxext6 : Breaks: libxext6:i386 (!= 2:1.3.0-3ubuntu0.1) but 2:1.3.0-3build1 is to be installed.
 libxext6:i386 : Breaks: libxext6 (!= 2:1.3.0-3build1) but 2:1.3.0-3ubuntu0.1 is installed.
 libssl1.0.0 : Breaks: libssl1.0.0:i386 (!= 1.0.1-4ubuntu5.10) but 1.0.1-4ubuntu5 is to be installed.
 libssl1.0.0:i386 : Breaks: libssl1.0.0 (!= 1.0.1-4ubuntu5) but 1.0.1-4ubuntu5.10 is installed.
The following actions will resolve these dependencies:

      Keep the following packages at their current version:
1)      libbsd0:i386 [Not Installed]                       
2)      libc-bin:i386 [Not Installed]                      
3)      libc6:i386 [Not Installed]                         
4)      libcomerr2:i386 [Not Installed]                    
5)      libedit2:i386 [Not Installed]                      
6)      libgcc1:i386 [Not Installed]                       
7)      libgssapi-krb5-2:i386 [Not Installed]              
8)      libk5crypto3:i386 [Not Installed]                  
9)      libkeyutils1:i386 [Not Installed]                  
10)     libkrb5-3:i386 [Not Installed]                     
11)     libkrb5support0:i386 [Not Installed]               
12)     libselinux1:i386 [Not Installed]                   
13)     libssl1.0.0:i386 [Not Installed]                   
14)     libtinfo5:i386 [Not Installed]                     
15)     libx11-6:i386 [Not Installed]                      
16)     libxau6:i386 [Not Installed]                       
17)     libxcb1:i386 [Not Installed]                       
18)     libxdmcp6:i386 [Not Installed]                     
19)     libxext6:i386 [Not Installed]                      
20)     libxmuu1:i386 [Not Installed]                      
21)     openssh-client:i386 [Not Installed]                
22)     openssh-server [Not Installed]                     
23)     xauth:i386 [Not Installed]                         
24)     zlib1g:i386 [Not Installed]                        

      Leave the following dependencies unresolved:         
25)     ssh-import-id recommends openssh-server            


Accept this solution? [Y/n/q/?] y
No packages will be installed, upgraded, or removed.
0 packages upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
Need to get 0 B of archives. After unpacking 0 B will be used. 

搞定, 先装一个依赖的指定版本的 openssh-client (旧版):

sudo apt-get install openssh-client=1:5.9p1-5ubuntu1

然后再装 openssh-server 就OK了。