This could be caused by incorrect APN (Access Point Names) setting. Happened to me in the past.
These can be configured via Settings > Wireless & Networks > Mobile Networks > Access Point Names.
Google APN Settings for (Your Service Provider) and check to see if you have the right setup.