I had this problem as well for 6 months+ and it drove me nuts!
I ended up terminating my Xbox gold subscription as I couldn't install any Xbox games from the Microsoft store, but my kid forced me to get it fixed to play Minecraft, so 12 hours later ;-)
my solution was:
-Click start, type Powershell and run it as administrator
-Copy and paste each of the commands below and hit Enter
get-appxpackage Microsoft.GamingServices | remove-AppxPackage –allusers
start ms-windows-store://pdp/?productid=9MWPM2CQNLHN
Reinstalling the store might also do the trick (that you can bing or google that separate).
Please MS, get this freaking thing FIXED so the store knows what wrong instead of just going into stupide mode and doing nothing!..
Hope it helps!