Depois de algumas dificuldades, descobri. Em suma (não tenho certeza se o primeiro comando é necessário):
sudo apt-get install libssl-dev
sudo apt-get --reinstall install libpython2.7-stdlib
A longa explicação é que, com base nos lugares em que o Python está procurando bibliotecas:
python -c "import sys; print sys.path"
e vendo que havia um arquivo _ssl.so
em /usr/lib/python2.7/lib-dynload
em um outro servidor 14.04.1 "saudável", descobri que o pacote responsável por isso é libpython2.7-stdlib
:
$ dpkg -S /usr/lib/python2.7/lib-dynload/_ssl.x86_64-linux-gnu.so
libpython2.7-stdlib:amd64: /usr/lib/python2.7/lib-dynload/_ssl.x86_64-linux-gnu.so
Depois de reinstalar libpython2.7-stdlib
na máquina original, o arquivo foi recriado e o problema desapareceu.
sudo apt-get --reinstall install libpython2.7-stdlib
(Eu realmente não sei como ou porque este arquivo _ssl está faltando no sistema - eu não sou a única pessoa usando o servidor ...)