Tentou instalar um pacote que tinha o X11 como uma dependência em um servidor (Instalando o erlang no Ubuntu 15.04 Vivid da DigitalOcean). Não é um sistema de produção, então não estava muito preocupado, mas um ou mais dos pacotes não foram instalados.
Quando percebi, decidi desinstalar o pacote e suas dependências, mas o x11-common e alguns outros não conseguiram desinstalar, porque sempre que ele tentava fazer service xxxxx stop , ele informava que a conexão expirou.
(Nota: agora está corrigido, veja minha resposta abaixo - mas ainda estou curioso sobre como isso pode acontecer)
Ainda não sei por que isso aconteceu, mas a reinicialização da máquina parece tê-lo corrigido - embora sudo reboot não funcionasse, tinha que usar o recurso de ciclo de energia da DigitalOcean. É possível que o sistema init tenha sido alterado como uma dependência do meu pacote?