I used to get that message too. It was a matter of setting up the proper data settings. However I had my iPhone unlocked with T-Mobile. I personally suggest updating and restoring your iPhone first. Then You might want to call your carrier and go over your data setting one by one with them. I think thats a good place to start.