Are they contacts from some synchronized account? Have you tried resynchronizing your accounts from the accounts page?