Well I registered just to tell the outcome of the same problem I was having.
I called Verizon, Make sure you are on the phone with the Blackberry or
PDA
support team. What they did was turned my Blackberry off and turned my old phone back on. I went into the get it now feature and deleted my mail account. After that we turned my Blackberry back on and the problem was fixed. It took a whole 20 mins to fix the problem...