Google Authenticator Problem contacting Google's server.

Google authenticator appears to have malfunctioned on my phone(LG3) as the codes are not working. This has happened before and the simple fix was under Settings>Time correction for codes<Sync now. However now when I do that I get the message "There was a problem contacting Google's server. Please check your network settings and try again".

I have spent hours searching and applying possible fixes that I have read online, but none of them work. This includes:

1. Trying multiple wifi networks/resetting router, leaving off for 15 mins
2. Trying a new networks sim card
3. Resetting phones time, making sure its on automatic time.
4. Deleting google accounts off phone and re-adding.
5. Clearing cache/data, force stop for all relevant google apps as well as download manager.
6. Reinstalling Google Play Services from apkmirror
7. Rooting phone to edit the host file to 127.0.0.1 localhost

I am really starting to become desperate about this now and would really appreciate any ideas. Thanks

Welcome to Android Central! Try going to myaccount.google.com/signinoptions/two-step-verification on your computer browser and either Change Phone in the Authenticator section, or click the garbage can icon there and set it back up again.

Thanks for your reply, B. Diddy.

I have tried this and while at first hopeful, it appears clicking Change Phone only adds a code for your google account to a different phone. It does not migrate over existing non-google account codes or refresh them. As well the garbage can icon only removes 2FA from my google account.

I appreciate your effort in helping me find a solution and am still putting in hours every day to try and fix this problem, if anyone has any more ideas.

Hmm. So if you remove 2FA, and then add it back again, the same problem persists?

Correct. Removing the 2FA on that page just removes the requirement of the code from my google account, not the entire app. The issue I am having seems to be with the Google authenticator app having codes one or more 30-second cycles older than what my non-google accounts are using. Why suddenly I am unable to sync the app to align with my non-google accounts is the mystery. That is what prompts the error message:
"Sync now
There was a problem contacting Google's server. Please check your network's settings and try again."

I made an account on this website because I read older androidcentral discussions with various solutions, all of which I have tried with no success (the attempts outlined in my first post). I am hoping someone has some idea what may be causing this. Thanks again.

*cries for help*

I can see that you've already tried pretty much everything that's been mentioned in the search results that I get. The next step might be a factory reset.