I searched a lot of info on the internet and I found a hint about the hosts file. The hosts file is a computer file used by an operating system to map hostnames to IP addresses. I red that in some phones in the hosts file the adress to android.clients.google.com is translated to a certain IP address(es). Bang! what if Google changes the IP address for this domain?
The first thing I needed to do was to root the phone and gain permissions to open the hosts file.
I used Kingo ROOT which is a simple software to root the Android phones.
After that, I needed a file browser to browse the /etc folder and find the hosts file. But, I could not sign in to install an App for the purpose; I was able to download the app Root browser via another site and mail the app to my phone. Then I installed the app that I get as attachment in my mail.
I opened the hosts flie and I found this:
There were 2 nasty entries that translated the domain android.clients.google.com to 184.108.40.206 and 220.127.116.11
That was the problem! If I ping to this domain I get 18.104.22.168 as response.
I commented with a # the two entries, saved the file, rebooted the phone and my problem was resolved!