Are you sure in the first place that the values you entered are accepted by SFDC ? Are you sure you did not update Account information ?
Normally, the most recent update wins on leads and contacts (in case the record was updated on both ends between 2 syncs, SFDC wins). Account information cannot be updated from SFDC, it's a one way sync.
You need to look at the activity log of a couple of these leads / contacts to see whether you got any type of error message during the sync following the update.
Here's the answer - I think...
I finally got access to SF and was able to look at the data structure. The "logic" for contacts in SF is that their country is the same as their associated account. The account country field SF uses the two letter ISO code, but also allows data imports - leading to multiple values for country choice. Marketo updates the country field in Marketo, but the SF sync over-writes that change.
Our SF admin is on a two week vacation, so I am unable to address this with him until he returns. Until then, no more country normalization in Marketo
At least you know why. Not as good as having it fixed, but you can stop spending time trying to guess, and may be take 2 weeks of too