I just wrote a lengthy post with suggestions how to solve it when suspecting XPrivacy as the reason behing this. However, for me, the update seemed to have done the trick. Logging in from a WiFi directly after re-installing GApps in the third update step, whithout having the XPosed Framework activated, might have to do with it. I also keep loosing the connection when using TOR network, and it sometimes does not come back immediately after stopping Orbot (but nearly instantly returns if I update any app from the play store while not using TOR network).