Are you running the version of Lineage with GMS installed, perchance? Lineage doesn't bundle GMS by default which makes it somewhat painful to get things working (especially since SafetyNet is deprecated, that was the last technology I had read about a while back).