I'm using Virgin Mobile Network in France and I have the same error.
Even reset the phone don't work. (so don't waste your time with this)
With the same google account it works with Wifi or with another carrier, so my carrier would be the problem, I called them but It seems the skills of Virgin Mobile France tech team are very low.
I hope future will show me the opposite