I recently upgraded my Sony Z3 Compact to Android Marshmallow and noticed something really odd. When not on WiFi, I wasn't getting any push notifications or any updates. I'd come home or get to work and then my phone would light up and beep like mad. Later, I discovered that there was no network connection on the mobile network. I could make calls and receive texts, but the data connections just wouldn't work. Luckily, it's an easy problem to fix.
Go to Settings -> More -> Internet Settings and then choose Accept. You'll need to be on WiFi to do this, but it should fix the problem. Unless you're on T-Mobile and just can't get service anyway. Here's a video showing the steps:
A NOLA native just trying to get by. I live in San Francisco and work as a digital plumber for the joint that runs this thing. (Square/Weebly) Thoughts are mine, not my company's.