After all of this, I had to get on support with Xbox/Games for Windows support.
They took a look at my account and they said that I had too many devices on my account and it was causing problems. I went in and removed all 15 or so devices at account.microsoft.com and reinstalled the game. It worked.
I'm leaving this comment to everyone whos already tried using wsreset.exe or the powershell windows store reset method that EVERYONE mentions but doesn't work for everyone.