I had the same problem today as well.  I figured out an
interesting reason why this happens, but not how to fix it
yet.  

One my main machine with all my contacts, i noticed that
when I open a contact that my other machine cannot see,
the title bar on that contact says - John Smith - Contact
(Western European) as if the contact itself was encoded
with Western European format.  The contacts that the
second machine CAN see are only listed as - John Smith -
Contact  ...no encoding at all.  Having said that... I
have no idea how that contact got the "Western European"
encoding and I have no idea how to remove it.  The only
thing I can think of is to create a new contact with that
information and then delete the old one.  Hope that helps.