Depois de muito sofrer consegui sumir com o problema do Play Services fazendo o seguinte.
1 - Entrando via TWRP marquei as opções em advanced wipe (format cache, dalvik cache, data e system) não reinicie ainda, continua....
2 - Instalei a ultima rom cm-13.0-20151204-NIGHTLY-falcon.zip http://download.cyanogenmod.org/get/jenkins/137632/cm-13.0-20151204-NIGHTLY-falcon.zip
e o gapps http://opengapps.org/ como na imagem
Instalei nesta ordem CM 13 e depois o GAPPS PICO.
3 - Só dei os wipes (cache e dalvik cache) após instalar os dois sistemas citados acima.
Pronto, após reiniciar parou de apresentar o erro infernal de Google Play Services.
Todos serviços google como, Play Store, Gmail, Hangouts entre outros com funcionalidade normal.
De momento não encontrei falhas.
Vale lembrar que recomendo fazer um backup de fotos entre outros, pois o processo vai zerar tudo que tiver no aparelho... No meu caso já tinha perdido antes mesmo hehe não fez muita diferença.
Espero ter ajudado.. Postem resultados por favor.