I just recently had my cell phone die on me, so I switched to T-Mobile and got a Motorola V360. This phone has bluetooth as well as the ability to act as a USB modem with a data connection (dial *999 or something, check online for the recipe to get connectivity). It supports EDGE as well as GPRS, and works with the cdc-acm linux driver. While it is not fully supported by moto4lin, I can use kdemobiletools to download my address book, make calls and send SMS messages. The phone needs to be switched to modem mode to be used this way, as the default is to provide USB mass storage access to the microSD card in the phone.
So all in all, works better than I would've expected. As with anything, YMMV.