For future reference, in case someone does a search, I had this same problem and here is how I resolved it:

-I deleted all contacts from Outlook. Not sure if this was necessary, since I think the problem was on the handheld in my case.
-I changed my hotsync to work with the Palm Desktop conduit and performed a hotsync. All contact records synchronized with Palm Desktop without a problem.
-I set the Palm Desktop to overwrite the handheld for the Address Book (Contacts). This worked fine.
-I changed the hotsync to work with Outlook, set the handheld to overwrite Outlook, and performed a hotsync.
-Now everything syncs fine.

Hopefully this will be helpful if anyone else has this problem. By the way, I'm using Win xp SP3 and Outlook 2007. I am using the Palm Desktop downloaded from Palm's site, and the HotSync Manager is version 7.0.2. Palm Desktop version is 6.2.2.