Right guys, I had this problem for the past week and cannot find it or a solution ANYWHERE on the internet.... very peculiar. However with a bit of tinkering I resolved my issue, if only temporarily.
First, you need to know your APN settings. You should be able to find these settings under
Settings > Mobile Networks > Access point names
From here, there should be an option to add a new APN (It may be a little "+" or may come up after clicking on "more options", something like that)
To find out the APN settings that you need, you'll need to go to google, and search "[network provider] APN settings"
For me, I typed in "iD mobile APN settings" and the first result sufficed.
After you have entered the details, you need to save these settings.
Press back on your device (previous menu) to get back to the Mobile network settings page. You can alternatively go to your home screen and do this: "Settings > Mobile Networks" as before.
Then, select Network operator and press OK if a box comes up. You'll need to let your phone search for a new network operator, and then select your network operator.
Voila!
If this hasn't fixed your problem, I will be keeping an eye on this thread even though I don't use this site, so just post back here any of your questions
Good luck!