Beh mettiamoci all'opera a scrivere questo poema:
Fare il root, scaricare hosts editor (l'apk visto che non si riesce ad accedere al playstore) e cancellare i file che troverete dentro hosts editor e si risolve tutto
Comunque ho capito anche perchè ho avuto questo problema: ho installato e poi disinstallato l'app Freedom (sì, sono un cheattone) e dopo ha cominciato a dare problemi (mi è successo oggi per la seconda volta ed ho risolto facendo quello che c'è scritto sopra)