I got the same problem after trying everything listed above could't fixed it. I was surprised to see it worked at office then came back home and used google dns ie 8.8.8.8 and 8.8.4.4 and it is fixed. Hope it helps somebody
I am currently having this problem. I followed your instructions above but the problem is I couldn't save the file. What should I do? Badly need your help. Thanks!
1. Must be rooted
2. Install file manager, my person recommendation is "root browser"
3. go to "ect>hosts"
4. open with text editor
5. you will notice there is no "#" in front of the numbers...add one and push the save button in the upper right
6. open play store and it will be working perfectly.