sprint recently changed their policies about tethering, i.e. using a phone as a modem via a cable or bluetooth. You do have to pay for you use - you can't just get unlimited data while tethering using a low cost vision plan. Instead, you need an actual data plan. Of course, this changes every other week. They are rolling out EVDO just about everywhere, but I think that their only bluetooth evdo devices at present are pda sized, with pda price tags, and I'm not sure if you can tether.

T-mobile is the low price leader [25 or 30 USD/month tethered or untethered]. They are rolling out EDGE/EGPRS, which isn't too bad, but their coverage area is pretty much limited to cities. They have lots of bluetooth capable phones too.

cingular has edge, and is rolling out UMTS/HSPDA in some areas. It is much more expensive than t-mobile with the unlimited data plan costing 79$ a month, but there are some cheaper plans available too. Cingular has several bluetooth phones. The original post in this thread stated that cingular doesn't support bluetooth tethering. This is certainly true of the low cost plans designed to just add data to a phone or pda. You need to talk to the data group which is geared more toward business users, and yes, pay for the "privilege". I set my account up under AT&T, so you may have some trouble convincing them to set up a "laptop connect" data plan onto a voice account, but I have a friend who did it with cingular just a few months ago. It does require that the CSR you deal with have a clue.

Verizon removes most of the data tethering features from all their phones so for a bluetooth modem, verizon is not a good provider, unless you want to hack your phone to put the features back in.

One thing you may want to keep in mind is that the network speed isn't as much of an issue if your phone only supports BT 1.1. I have several BT phones, and all of them except for my UMTS motorola A845 only seem to support 115200bps as max connect speed
when acting as a modem - I think this is a limitation of the BT 1.1 DUN profile. A BT 1.2 phone should work a lot better, should you be able to get one. I higher speed network wont do you much good if your limited to 115200bps for the BT connection.

Depending on where I am, I use either a moto A845 or a nokia 6230 with cingular. Both phones work fine to my palm lifedrive, a BT 1.1. device. I have the unlimited plan, which only makes sense since I need it for business. If you plan to use a lot of cellular data, and money is an issue, edge from t-mobile is probably your best bet. Otherwise, pick the cingular dataplan that best suits you. I plan to upgrade to the nokia N80 once it comes out next year. SInce the N80 has some series 60 PIM functionality, I think it will make a fine complement to the 770. [should I ever get mine]

howardfourms.com and pcsintel.com have tons more info should anyone care to look into this further.

This whole subject makes my head hurt. This is way more complicated than it should be for nov 2005.