After joining Windows 10 (1511) to a Samba domain, domain users are unable to sign in to the Microsoft store. It just fails with an unspecific error. This not only affects the store app, but also the user profile settings (where you connect your local account to your Microsoft account). Even Visual Studio 2015 hangs with a white dialog when trying to log in. Any connection to a Microsoft account seems to be impossible.
A related issue is that the RDP client takes an unusual long time to start, but when its there, it works fine.
How can I fix this?