I had the same experience. I am using CyanogenMod as well and as much as I dislike Google I did install the Play services. I can't even remember why but I think I needed it to use the google voice app.

Anyway, google play apparently tried to auto-update and bricked itself; now it just says "no connection" when I launch the play store.

Last week I tried to install TestSecure but it would not run. It just gave an error message about needing to update play services.

I ended up installing the Telegram app in F-Droid.