Digging a bit deeper, I found that my APN on my phone had a proxy server specified in it. I created an exact copy of my APN, just without the proxy settings, and it works!
Wow!!
Sorry for the old post revival but I had such a hard time finding that, thanks a lot for posting this! I had the same issue (Bell Canada)
Thanks a lot!