I was also having the same problem, I tried everything including, clearing cache, data, on a 3G network even on an LTE one, took it to my network technician, all failed. I discovered that this is actually not a network problem, it's an app issue. This is caused by the background data app restrictions settings. Some apps (esp. Google apps) depend on each other to function properly when they're being updated. So you need to unblock/unrestrict ALL the apps (yes, including the ones you're not updating). And the fastes way to do that is to follow these 5 easy steps:
Go to --> Settings >>> Apps >>> Menu (the 3 block-like dots on the top right corner), a drop-down menu pops >>> Select "Reset app preferences", a pop-up block will appear with a warning >>> Select "Reset apps".
...
Do all the updates you need to do
...then go back to your Data Usage Settings to restrict the apps you wanna restrict.
Hope it helps you like it helped me