A picture of a person, taken in public, does not capture anything that the person did not choose to show in the first place (unless we are taking about extraordinary circumstances, like a person falling, etc, that does not apply to the OP).
If the lady did not want her shoes to be seen, she would not have put such shoes on, or her husband/father/mother/whatever would have not let her put them on. I don't see why random people looking at her shoes is ok, but someone photographing them is not. Call me culturally insensitive, but I honestly don't see the difference between "seeing" and "photographing" -- and just wait for google glass 3.0, that will be a brain implant
Regarding the advice "make sure the person knows you are taking a picture of them", I'm sorry, but that doesn't always work. I have personally traveled all over Europe, the US and a couple of places in China and I always make sure the person sees me when I take a picture of them (so they have the opportunity to say, or nod, "no", which I always respect). However, in the OP what was the photographer supposed to do? Run to the lady and tell her: "sorry to interrupt, but can you please keep walking the way you were just walking before, so I can take a picture of your contrasting shoes/dress"? c'mong now.
My view is simple: if you are hiding and/or taking a picture of a person showing them in a way they might have not wished to be seen, then you are not playing nice. If you are capturing something that everybody is seeing and the subject is aware of the visibility, well ... it's fair game.