How frustrating!
I typed up a fuller post on a similar issue here: Corrupted cloud save - #5 by tamalien
This may also work in your case.
If that doesn’t work then it may be a gaming services issue …the latest version I have installed is 2.51.15001.0
You can find this information under the Microsoft Store, click the three dots top right and select “Downloads and Updates”.
If your gaming services is up to date (and the re-install technique above didn’t work) then I have no idea, at this stage, what else to suggest.
Edit: I am assuming that you are aware that you can file an official support ticket on Zendesk. Click top right “submit a request”.
Edit: I also had a further thought… Since you did a fresh windows install it may be that your computer is using your ISPs default DNS servers. These have been known to cause some problems. If you search online about how to change your computer’s DNS to, say something like google’s 8.8.8.8 then that may help.