I wrote one of the (non-root, virtual network-adapter based) apps like PdaNet, and I can say that a number of people on VZW have reported this. I wonder what would happen if my app were one day open-sourced so that anyone could publish an apk to the market in 15 minutes...