Select one object, select a material from the library, select a material slot if there are more than one. Click the circular arrows button. The material is replaced and applied immediately.
If the blue icon is toggled on, the replace button turns green, and the material will be replaced on every object that uses it, even if unselected.
In order for multiple replace to work, materials have to be the same, not one a copy of another. Check their names: if they are different choose the correct material from the material slot dropdown menu.