did you re-boot your phone? I have had that problem while syncronizing my contacts and rebooting the phone solved it =)