Are you both on the same Exchange server? We had a similar problem with items not syncing due to a corrupt information store. After they moved the affected users to a different Exchange server, they were OK.