Ubuntu 16.04.3 aquí:
Creo que solucioné esto eliminando el paquete python-openssl (y sus dependencias) con:
apt-get --auto-remove remove python-openssl
Luego instalando la última versión con pip:
pip install pyOpenSSL
Por supuesto, si instala otro paquete apt que dependa de él, lo recuperará. Espero que si usa pip para todo lo que pueda de ahora en adelante en lugar de apt, debería estar bien.
Editar:a partir de enero de 2019, parece que este problema ya no existe.
Si incluso pip no funciona, intente lo siguiente:
sudo easy_install -U cffi
sudo easy_install -U cryptography
Funciona para mí.
Pude resolver esto eliminando la biblioteca de python de openssl y reinstalando (la purga antes de la instalación no funcionó):
$ sudo rm -rf /usr/local/lib/python2.7/dist-packages/OpenSSL/
$ sudo apt install --reinstall python-openssl
Para solucionarlo en RHEL/CentOS:
sudo rm -rf /usr/lib/python2.7/site-packages/OpenSSL/
sudo yum install pyOpenSSL
Esto lo hizo por mí en CentOS 7. ¡Salud!