I contacted Apple customer service about the same problem trying to tether an ipod touch 4.3.3 to a verizon vx8300, which has no problem with laptop tether.
I was told that the vx8300 does not support EDR protocol, which is necessary for accessing internet with iPod (and presumably any iOS device)
I suspect the problem is logon credentials for the phone to use bluetooth modem. There is no place in the setup for iPod bluetooth that allows dial number (#777 for verizon) or username/password.
Any further advice (even jailbreak) will be appreciated.