Pull battery and sim card, let phone sit for 90 seconds, reinsert card and battery. If that doesn't solve the problem, and you're sure it isn't simply a data outage in your area, contact Verizon and see about getting a new sim card.
If your problem persists, and you do want to keep trying to fix it, "grit your teeth" and do a Factory Reset. These have gotten pretty painless lately by following these simple steps: 1. Make sure Backup and Restore are checked in the Privacy setting. 2. Backup everything on your sdcard that you want to keep as a Factory Data Reset wipes the sdcard. There are apps in the Market that will backup everything including SMS and Text messages. 3. When going through the setup after the reset, turn on wifi as soon as you can (assuming it is available). 4. After you have entered your Gmail account info, you will be presented with a screen that has two check boxes. Basically they are "Do you want Google to backup and restore this phone”. Make sure you check both of those. 5. Open the Market app and accept the market terms. 5. Your apps will then automatically reinstall (paid and free). Set the phone aside for a minute or two and let the apps download and install.
If it still doesn't work, then it's time for a warranty replacement, IMHO!
