Google Apps OAuth2 Authentication suddenly stopped working for many installations ("policy_enforced" error)

It looks like as of some time yesterday one of them with Google Apps (OAuth 2.0) completely stopped working for various Google Apps Marketplace apps.

Users get the following error when trying to log in:

400. This is mistake.

Error: policy_enforced

Application: ....

You can write to the developer of this application at: .....

Access is denied by a security policy set by your organization's Google Apps administrator. Contact your administrator for further assistance.

What we found is not the reason:

• This is not a security policy as the error says. This happens with many installations across all organizations, and none of them have made any changes.
• We haven't made any changes to the app, and a search on Twitter reveals that this is happening with multiple vendors.

What we found that these installations have in common (so far) is that they are all installations that were recently ported from Google Apps Marketplace V1 to GAMv2. This happened a few months ago, although there were no problems, as the problem appeared yesterday yesterday.

Is this a new bug in Google's authentication mechanism, any idea what to do with fixing it?