engine-setup fails with "RSAError: data too large for modulus" message

Issue

• While upgrading from RHEV 3.5.8 to 3.6.5 we see the following trace in the engine-setup process

2016-05-03 11:40:17 DEBUG otopi.context context._executeMethod:156 method exception
Traceback (most recent call last):
  File "/usr/lib/python2.6/site-packages/otopi/context.py", line 146, in _executeMethod
    method['method']()
  File "/usr/share/ovirt-engine/setup/bin/../plugins/ovirt-engine-setup/ovirt-engine/config/aaa.py", line 229, in _validation_late
    padding=RSA.pkcs1_padding,
  File "/usr/lib64/python2.6/site-packages/M2Crypto/RSA.py", line 63, in private_decrypt
    return m2.rsa_private_decrypt(self.rsa, data, padding)
RSAError: data too large for modulus

• In the admin Web UI, Datacenter is in non-responsive, storage domain are in unknown, hosts are in non-responsive, VMs are in unknown state but running/accessible