I had to give network permissions to the play store as well, not (only) play services