I needed a GPRS-capable phone to use as a modem with our Lenovo S10 on a trip out of town, and after some research, Hassath and I bought the Nokia 7210 Supernova, which does GPRS and Bluetooth well enough (and has a host of features that we didn't care about). Here's a very brief report.
Our S10 runs Ubuntu 9.10, which detected a new "mobile broadband" connection when I plugged in the phone using the (absurdly short) included USB cable. To my surprise, it let me select my country and provider (Vodafone), and I was online in a few seconds with no fuss. Disappointed at the lack of an opportunity for heroic action, I tried Bluetooth next. Following some advice on the Ubuntu forum, I installed blueman, and… that just worked, too. I could detect the phone, pair with it, browse its filesystem; and if I activated dialup access, I could use the same mobile broadband connection as above. All of this took barely more than a minute.
While travelling, I noticed that the connection via Bluetooth sometimes had trouble with flaky GSM connectivity. If the phone lost coverage, the connection would die, and both devices would need to be rebooted to make them talk to each other again. But that happened only when we were on a train, hopping between towers. Other than that, things worked very well (at least, if I tried not to think about the INR5/MB usage charges).
One little quirk: when I activate dialup access in blueman, it pops up a window that says "The device Nokia 7210 Supernova does not appear to support GSM/CDMA. This connection will not work". But it does.