Can you clarify the scenario a bit? My understanding is that you just did a full wipe of a Chromebook, signed in, and are having problems syncing.

You mentioned two different messages on the settings screen; can you clarify where those were? The AUTH_ERROR on sync-internals may be unrelated, but there might have been a real problem getting auth tokens for your account. Why do you think that could not have been the case?

I am pretty sure there were no auth issues on the account. It all came down to DNS failing to resolve clients4.google.com. Once I solved my DNS problems, everything started working perfectly.

If you purposely break DNS in the same way, causing clients4.google.com to not resolve, you might see similar problems.

I could not reproduce the issue either.
I have tried signing in to sync after a powerwash and I could be able to successfully sign in without any errors and the sync internals page too does not have any errors.
I have also tried reimaging the device with the latest chromeos and then sign in to sync build. Still haven't seen any errors and sync internals looks healthy.
Could this be some intermittent issue?

Correct, it is an intermittent issue. The problem is that when this issue occurs, the system provides misleading diagnostics.

You should be able reproduce this network issue by changing your DNS or firewall configuration to block traffic to clients4.google.com. Once you do this, you'll see the problems as described above.