Unfortunately the app troubleshooter didn't find anything. I check for updates daily from Settings > Update & Security > Windows Update, so I guess the November update must be installed, also I'm running the 64-bit version, so it's not that either. What do you mean that I must have an Xbox account? Do I have to be login-ed into it while browsing the store? I've also uninstalled some of the default apps that come with Windows 10, one of which was some kind of Xbox app, maybe this has a relation?
I just read somewhere that to play the game even on pc you need an Xbox account, now I'm not sure if this is your issue or not. I guess you could always create one and see if it makes a difference? I think you can download the Xbox app from the store.