Sounds like somebody tried to feed you a big steaming pile. I tether all the time with my MBP and 8310 on ATT. I just had to load a script, pair via Bluetooth and enter a few modem parameters. It's pretty worthless without 3G though. That's the only reason I keep my Windows Mobile device around!

I've heard from others on Verizon that you must have a specific tethering data plan though. Really I don't know why tethering on any platform is such a great mystery. There's nothing to it, just a few details change from carrier to carrier.

The main problem is you can't get a straight answer from most carriers, let alone decent tech support.