I am following the sample https://msdn.microsoft.com/en-us/library/office/ee693002%28v=exchg.80%29.aspx and try to update contact's business address and it is not working. Is it a known issue?

Do you get an error when you do the Update?

no error, the address just did not get updated

I verified the request that the info i sent is correct

Have you looked at the EWS Request/Response?

Ok, i analyzed the above issue. As part of it i modified the code for updating contact's business address like the following:

                // Update the contact's business address.
                //PhysicalAddressEntry PABusinessEntry = new PhysicalAddressEntry();
                PhysicalAddressEntry PABusinessEntry = null;
                PABusinessEntry = contact.PhysicalAddresses[PhysicalAddressKey.Business];
                PABusinessEntry.Street = "4567 Contoso Way";
                PABusinessEntry.City = "Redmond";
                PABusinessEntry.State = "OH";
                PABusinessEntry.PostalCode = "33333";
                PABusinessEntry.CountryOrRegion = "United States of America";
                contact.PhysicalAddresses[PhysicalAddressKey.Business] = PABusinessEntry;

                // Save the contact.
                contact.Update(ConflictResolutionMode.AlwaysOverwrite);              

Using this updated code, i see that the contact item is updated successfully.

Try the updated code and let me know whether this works for you or not.

Cheers!!