same problem
I had this problem, I called verizon and was on the phone with them for probably a good two hours. finally he told me he filed some ticket for it, and it started working again the next night through the next morning. I got a text saying my ticket had been resolved and it stopped working again.
I went to Apple and they gave me a brand new iPhone 4. and the problem is happening AGAIN. mostly only with 3g, though. I'm gonna call Verizon again.