Juste done it with a treo 650 and it worked perfectly.
But you need last Apple OS for the treo to be recognised as a bluetooth modem. I (only) have Tiger so had to download the "Generic GPRS modem" near the bottom of the page
http://www.taniwha.org.uk/ that as other good stuff about others phones and serial modems. For myself I got good results with "Generic GPRS CID3" script. You need to drop the file in /Library/Modem Scripts/ and follow others instructions from the "Read me" file coming with. Except dialing the strange numbers like #*876543 (don't remember).
You need to put a user name and password. For Orange in France it's Orange and Orange ! You can do this in the network/bluetooth/ppp panel or in the "internet connect" application that you need to start in order to connect anyway (unless you checked the box "connect automatically if required" box in PPP options of Preferences Panel.
For the treo you have to "pair" it with the mac first Mac OS give you a string of numbers to enter in the treo when it discover it first time. Treo must have bluetooth enable of course and in the bluetooth pref panel of the treo you must clic on the Remote access dialogue (after "pairing"), the bluetooth icon change for one with a little notepad an littler bluetooth then you can clic "connect" in "internet connection" for the mac.
Works perfectly for me 🙂
Merry Chrismas !