It doesn't sound like device problem. It sounds like your network problem. Even tho the phone shows the icon, there might be a problem on your carrier's end. Happened to me few times. The carrier support ended up resetting something on my account, and I would get my service back on track in manner of minutes.
I would give them a call, and explain the exact problem.
This might be a silly question, but did you by any chance (accidentally) turned of your DATA connectivity ?