I had a Treo 650, and also had the same pairing issues. I was able to get it paired, but the trust was never created. I had to accept the connection on my Treo before internet would go through. I was sick of the PalmOS anyway, so sold it on eBay and got a Nokia 6682 - problem solved. The only thing I miss is the full keyboard.