Hi Prakhar,
Thanks for the suggestion! I've tried running that Microsoft Account Troubleshooter and get an error mid-way through that it "can't connect to the sync service. There might be an internet connection problem of the service may not be available".
I've got no problem with my connectivity though and I'm not using any VPN or weird networking settings.
In the troubleshooting report it finds the connectivity issue as well as "Rootcauses found and created logs".
Any ideas on what to do next? I've tried resetting all my network settings, and doing an IPConfig release. Not sure why it thinks there is some connection issue.