Welcome to the Apple Support Communities!
I found this article while researching the symtpoms you state here named iPhone: Troubleshooting a cellular data connection found http://support.apple.com/kb/ts3780.
- Toggle airplane mode: Tap Settings, turn airplane mode on, wait three seconds, and then turn off again.
- Restart your iPhone.
- Ensure that your software is up to date:
- Remove the SIM Card and reinsert it. Allow the iPhone to acquire the network again.
- If your SIM card has SIM PIN enabled, try toggling it off: Tap Settings > Phone > SIM PIN.
- Try another location. If a different location works, but the original location still does not, contact your carrierto report the issue.
- Reset network settings: Tap Settings > General > Reset > Reset Network Settings.
- Restore the iPhone as new.
- Contact your carrier to:
- Verify that the iPhone is properly set up on the account with the appropriate, current data plan.
- Verify that there are no account-related blocks.
- Find out if there are specific error messages in the carrier logs that could help determine why the issue is occurring.
I know you have reseated and replaced the SIM card already so you can skip that part.