@mikazu if changing DNS, internet connection (diffence SIM, WIFI) doesn't make things right then you may clear Google apps' data/cache & check whether its working or not.
By the way Have you tried taking different route?
Settings > Accounts > Add Account > Google