Default [Q] Not Connection To Google Play Services When on 3G/Mobile Data

I am having a problem connecting to google play services when my phone is using the mobile data connection (3G).
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.

Any Ideas?