I have had this issue too. It's something to do with how the phone accesses the Internet.
For me it's not just safari. Sometimes it's speedtest.net, other times its mail, and sometimes it's a random app that uses internet access.
I launch several apps and once one makes it through, they all do.
It seems to be a carrier issue, but could be an iOS issue.