I am experiencing the exact same problems on a brand new Dell Latitude. It is domain-joined, but besides the first local user that was created during OOBE setup, and the first domain user that logged in right after joining the domain, all other new local users and domain users that login to the computer for the first time have the issues you describe.
None of the solutions or fixes I found helped (using wsreset.exe to clear the apps cache, running PowerShell cmdlets to re-register the apps, etc.). Even an in-place upgrade install using the Windows Media Creation Tool did not help. Some work-arounds suggest disabling the Microsoft Store or the App Readiness service, but they are not acceptable fixes to me.
I finally tried something that helped. It does not directly address the problem, but it does seem to clear up the problem and I'm satisfied with it until Microsoft can fix it properly (hopefully in 1803). I'll post it here in the hope that it helps others.
First, delete the faulty user profiles. Then open Group Policy Editor (gpedit.msc) as admin. Change the following 3 settings:
- Computer Configuration > Administrative Templates > System > Logon > Show first sign-in animation = Disabled
- Computer Configuration > Administrative Templates > Windows Components > Search > Allow Cortana = Disabled
- Computer Configuration > Administrative Templates > Windows Components > Cloud Content > Turn off Microsoft consumer experience = Enabled
(Source of these settings: https://docs.microsoft.com/en-us/windows/client-management/mandatory-user-profile)
Reboot, then login with a user that previously had issues. Hopefully you will find, as I did, that everything is functional except that Store apps do not seem to be set up (the Start Menu tiles have a generic download arrow). But if you click each app, the Store opens to the correct download page, and the app can be installed properly.