Are you running Tiger or Leopard?
I think some basic troubleshooting would help out. I apologize in advance if you've done all this and it's of no use
First, try just resetting your sync history in iSync. (Open up iSync from the Applications folder. Click on the "iSync" button in the upper left, click on Preferences, and then Reset Sync history)
If that doesn't help, try uninstalling/re-installing iTunes and restoring again.
Still no success? Try restoring in a new user on your computer.