The first possibility that came to mind is that your Palm Desktop user name might not be the same as your Handheld user name (they have to match to sync).
But since you say you're able to sync other data between the phone and Palm Desktop, then we're at least sure the PC-to-phone user name sync is fine.
The second possibility that comes to mind therefore is that you may have Contacts set to "do not sync" in your Hotsync settings. You can check this by looking at your Hotsync setup.
Disclaimer: I have a Palm Treo 600, so the steps below are more accurate for a 600. I'm just hoping that the Treo 650 will be similar enough that the steps below will work.
To check your Hotsync setup (in Windows):
1. Right-click on the Hotsync logo in your system tray. If it is not yet in your system tray, launch Hotsync from the Start menu.
2. In the pop-up menu that appears click on "Setup" or look for a similar term (like Configure). A new pop-up window should appear.
3. In the pop-up window that appears, you can specify the sync action for each type of information (Contacts, Calendar, Email, Notes, etc.). Look for the settings which control how Contacts are synchronized. It might be that yours is set to "do not sync".
Try setting the Contacts sync option to something that's more appropriate to you. In mine, the options are "Computer overwrites handheld", "Handheld overwrites Computer", and another option which basically copies whatever is missing across both databases.
Please be careful not to choose Handheld overwrites Computer since it might cause Hotsync to delete from the computer anything that's not on the phone.
Hope this helps. I know it's not an exact answer for the Treo 650, but perhaps there will be enough clues in this to help you troubleshoot.