Bought myself a new phone (well, the company did so, because not being able to use ssh via my old one really sucks if you got a subscription to mobile internet just for those cases), a Nokia E51. Cool thing is that it supports up to HSDPA, which really has a lot better ping times than GPRS. Not sure about throughput, but I don't care about throughput. I mainly check email and ssh, both use little bandwidth but really benefit from better latency (lower ping times).
First, go to Network Settings and select Bluetooth. Now configure the Bluetooth device. From the little cog-menu in the bottom, select "Change serial devices" (name might be a little off, I'm using a Dutch version of MacOS X). Add a serial device with a name you can remember, privding service "Dial-Up Networking" and protocol RS-232. Close that window and select Advanced in the bottom right. Add a device in the bottom, using protocol RS-232 and changing the name to whatever you chose before. Close that window and go back to the Bluetooth connection setting.
Now choose Advanced from here and make sure your device maker is Nokia, but the device itself is "GPRS (GSM/3G)". Not "E51", at least it didn't work for me with that setting. Now connect with your regular settings (which are empty for KPN in The Netherlands) and presto, you're done.
Please leave a comment if this helped you!