I know this is frustrating... but if this lady was the unique subject of your image, (I won't consider the stuffed toy) then the angry woman was right: you have to ask for permission before capturing her image.
It is allowed to shoot people in a public place without prior consent if a) they are not recognizable on the image or b) the purpose is to illustrate an event, showing many people on the image, as it is impossible to get approval from a large number of people.
Cherry, I suspect what you describe is a legal nuance that probably varies from country to country. It might or might not be true in France, say, but in the UK photographing people in public places (e.g. the street) without permission is allowable whereas on private property (e.g. a shopping mall) is not.
Right, laws vary a bit from country to country. California and some Canada provinces have their specific legislations. But, at the end of the day, the underlying principles are very much similar.
As other members have said, it is not prohibited to take photographs of people without their permission. What is regulated is the use of the images.The problem is, when someone notices he/she is being photographed, they cannot guess what the photographer does intent to do with those images...
Especially, in the situation described by the OP, when the picture would be used in a newspaper and/or published. That's why I suggested to explain first, and shoot later. Yes, the image is less candid...