a couple of days after i got my droid this happened, i walked into the verizon store and told them my problem and they told me one of their 3G towers went down and it would be 2-4 hrs before they could get it repaired. 4 hrs later it worked fine.
The only way to really find out in your situation is to go to your local store and ask them.