I went through the same process, I even installed a different GApps version. I was running the Core GApps package from XDA , thought it might've been that so I installed official from CyanogenMod but the problem persisted. It's on the Google side of things for sure.