So after some debugging, I found the problem which is the latest version of the Google Play Services, version 8.3.0

I downgraded Play Services to the latest stable release I had in the app (GPS 8.1.0) and sent out the new builds to users having the installation issues and they were able to instal the app successfully.

This seems to affect a few apps like Mixcloud too, but it could also mess up Beta, Fabric's app helping you distribute your app.

So for now, probably you should hold on with updating Google Play Services to 8.3.0 until they fix this.(?)

Here is a discussion with the Fabric team about the same thing.

EDIT:

Fabric fixed this bug in the version 1.5.1 of their Beta app.