If we cast everything into the active voice, there is no confusion.

a) I replaced the old rug with a new one. -> The old rug was replaced with a new one.

b) Plastic bags replaced paper bags. -> Paper bags were replaced by plastic bags.

So, the question is NOT "with" vs "by". The real question is whether

A) Somebody replaces X with Y.

or

B) Y replaces X.

When cast in the passive voice, (B) becomes "X is replaced by Y".