Hey guys, if you've tried all the other stuff, like using your admin-shell, reset/repairing, OS scans, and the like, but it still wont work, I might be able to help you. So, I've got three drives. My C with Windows, plus a D and an E. At one time, I had an XboxGames folder on each drive. I was trying to "install" No Man's Sky to drive E, where I already had the files. If I attempted to open the app from my start menu, it would send me to the Gaming Services' Awful Review. If I attempted to go through the Xbox App, after telling it where the files were, it would give me various hash-error codes and fail to even "install" to where I KNEW the files were. The most frustrating of which is where it told me there wasn't enough space even though I knew for sure there was. I slept on the issue, thinking about how I had changed the default install location to the correct drive and still had no dice. Then I remembered that it's not unusual for apps to fool with your C drive regardless of your specifications. So I checked in my C drive, looking for the Xbox Games folder. I opened it only to find a file with an obfuscated data name (Usually temp download files are like that.), along with a ~300Kb folder titled "No Man's Sky". I'm not sure whether it was the temp download file or the fumbled folder, but I deleted both. Lo and behold, everything works as it's supposed to now, start menu is fine and no Gaming Services, Xbox App finds the files instantly, no more errors anywhere.
TL;DR
Try checking for a file named like "7A7853F9-B5FA-42F3-B02E-D57BEACF4293" in your C drive's XboxGames folder, and delete it. May also delete any files within that folder that are not the size they should be.
Good luck guys, if this helps you, spread the word.