Solución:
Puede tener otro Crypto módulo en su paquete de Python. Puedes comprobarlo con
import Crypto
print(Crypto.__file__)
# should print /usr/lib/python2.6/dist-packages/Crypto/__init__.pyc
Si encuentra otro módulo Crypto, cambie el nombre / elimínelo o ajústelo sys.path
Además, su versión de pycrypto puede estar desactualizada. Cheque Crypto.__version__ – Crypto.Random existe desde 2.1.0alpha1.
Mencionaste que instalaste Crypto en
/usr/local/lib/python2.6/dist-packages/Crypto/.
Pero, por tus comentarios, parece que también tienes Crypto instalado en
/usr/lib/python2.6/dist-packages/Crypto/.
Por lo tanto, tiene dos instalaciones y la última tiene prioridad porque /usr/lib/python2.6/dist-packages/ aparece primero en sys.path.
Tuve exactamente el mismo problema y lo solucioné cambiando el nombre /usr/lib/python2.6/dist-packages/Crypto a otra cosa EG Crypto_bak solo para que pueda retroceder si algo sale mal.
Parece que la instalación de Windows tiene ese paquete como crpyto, no Crypto. Después de mucha solución de problemas, cambié el caso de la carpeta del paquete (en Python[version] Lib site-packages) y viola.