Hey there,
I actually ran into this same problem and fixed it on my own. I found that if you go to the verizon site and go to the manage your devices section then opt to activate a new device (assuming you have an old phone handy) activate some old device for ~10 min. Then turn around and re-enter the ESN for your device in the page. Wait ~10 min and then you should be OK.
Doing that causes the network to automatically refresh your DMU keys along with your A-Key. It only takes ~20 min to resolve the problem on your own without spending hour upon hour with support to get no where in the end.
Hope anyone else plauged by this problem sees this and can put it to use
