other8026 Well, the problem seems to be that I can't connect to Graphene OS services via my ISP and mobile provider.
I changed Network connectivity checks to Google and now everything is fine. It's strange, why can't I connect to GOS services, they are not in my country's blocklist, not right now, at least.