I am using the orange signal bars in the quick settings panel to indicate that it has no connect to the services. I have also downloaded this app that also confirms that there is no connection.
When I enable WIFI it connects straight away.
If I enable WIFI hot spot mode on my phone and get a friend to connect to my hot spot, they are able to connect to google play services fine.
Periodically it will connect to the services but 95% it wont.
I am currently running PA RC2 but have flashed stock 4.4, 4.4.2, 4.4.3 and 4.4.4 and the problem is the same.