Unable to sign in from Power BI Desktop and Enterprise Gateway after implementing Conditional Access

We have a production implementation of Power BI for which we turned on device based Conditional Access (CA), and added relevant AD groups. After turning on CA, users in the device based AD group are unable to sign in from Power BI desktop and also cannot sign in upon installation of a new Enterprise Gateway.
We get the following message: Unable to sign in. Sorry we encountered an error while trying to sign you in. Details: AADSTS50000. Device platform Unknown used by the user is an unsupported device platform. Supported device platforms are iOS, Android, and Windows flavors.
We are on a Windows platform and tested from Windows 8 and Windows 7 machines, and encountered the same error on both. This issue applies to October 2016 and September 2016 versions of desktop. To prove that CA triggered this issue, we used a test user not in the device based AD group. The test user was able to sign in successfully.
This issue is critical as it prevents us from being able to publish directly from Power BI desktop and prevents users from installing a new Enterprise Gateway.
Please let me know if you need any additional information. If you need Trace ID, Correlation ID or Timestamp, I can provide it via email.