What carrier are you using? Check to make sure your APN settings are correct for that carrier. Usually the phone will set these things itself, but sometimes it's worth it to look them up online and compare that to what your phone is using.
To check: Settings -> Wireless & Networks -> More -> Cellular Networks -> Access Point Names -> tap the one selected to check/edit settings. If everything matches, sometimes it's useful to reset to default (under the menu button when you're on the Access Point Names screen) to see if that clears any issues up.