First thing to say is "are both systems up to date?".
Second is that we (my wife is the Palm user) found that bluetooth was very slow. Too slow - and gave up. Bought a hard wire USB cable for the Palm and it works about 95%, but still not perfect. Usually connects and syncs, but leaves an error log.
Our feeling, not proven, is that Missing Sync does not like other stuff using the connections. She finds that best success rate of syncing is to do it as soon as the computer is powered up before opening any browser or application.
We still use the Palm Desktop as the thing to sync with, but next upgrade we may change to the Apple Address Book.