I have problem with anything working through HTTP/HTTP (i guess) when I'm connected to cellular data (it's ok on WiFi), like apps like Instagram, Google Play, Shazam, i can't surf the web too. But apps like Telegram and Spotify which is working through socket (i guess) is working well. I thought that problem is from DNS settings and tried an DNS Changer app but it didn't solve the problem.
Problem appeared after few weeks since installing CyanogenMod 13 on my phone (Nexus 5x in this case) and after it i've tried different ROMs/SIM Cards/Kernels/Tweaks to fix it it was not effective.
I had the same problem on my S4 Mini since installing CyanogenMod 13, and it still has.