Google Account Log in doesn't work on LTE/Data Note I am using Android ver. 5.0.2 OnePlus One Cyanogen OS 12.0-YNG1TAS2I3 

When I am on Wifi my device has no problem signing into my Google Account. 
But when I am on Data/LTE my google account has log in issues.

For instance:
YOUTUBE APP: If I am logged in, I get a "Network Connection Error" even though my internet works fine. If I log out of the Youtube app by clearing the app data I can watch videos again, but trying to log into my google account gets me the Network Connection error again and does not allow the log in.
I can however open the web browser, go to youtube.com, log in, and access my youtube content.

GOOGLE MAPS APP: On LTE I can view all my starred locations on Google Maps, but when I try and add a new starred location it tells me to select my google account. When I select it nothing happens. 

Google Now sometimes works, but sometimes shows the network connection error.

POKEMON GO: Trying to log into Pokemon GO via Google Account on LTE fails, but works on WiFi. 

Not sure if relevant: It's my first time having cellphone with data plan. Also currently in Japan.
I had the exact same problem: Cannot log in to google account when on data (works on Wifi)

After contacting both google and my network provider, it was clear that the problem is on the device. For me there was a built-in security app from Lenovo, blocking 'google services'. 

Check all your firewalls, antivirus programs and the settings>data that nothing as googleservices or googleframework is blocked. Uncheck 'restrict background data' in case it is enabled for all apps or google-specific. Also allow syncing data for apps while on data ofcourse.