Just posting my experiences in the hope it will help others.

My setup:

Asus EEE PC with internal bluetooth - running XP Pro and Widcomm
Palm Treo 650 GSM running on Vodafone NZ

Follow the guide here: http://www.palm.com/us/support/handbooks/treo/Treo650_GSM_DUN_UG.pdf

Things to note which are not obvious to those who have used bluetooth DUN with other devices:

  • You must set the modem initialisation string to AT+CGDCONT=1, "ip", "XXX" where XXX is the APN you wish to use (e.g. "Internet")
  • You must set the number to dial to *99***1# - as opposed to the *99# normally used with vodafone NZ.
If that still does not work for you, check out PdaNet from June Fabrics - http://www.junefabrics.com/palmnet/ - I had success with that when using the USB cable.