"They have been replaced by..." or "They have been replaced with..."

Solution 1:

In the examples you are providing, the word "by" refers to the person or object that is performing the action (replacing). Since objects are usually inanimate or incapable of performing actions by themselves, the word "by" would be less likely to be used. The word "with" is used to indicate which objects are the result of the action (replacements).

A good rule to follow when determining which word to use is to attempt to put the sentence in active form. The object or person denoted by the word "by" will always be the noun.

For example:

All the old school buses have been replaced by the mayor with new ones. -> The mayor replaced all the old school buses with new ones.

If you attempted to use the word "by" instead for your blank space, the following transformation would be the result (which is incorrect).

All the old school buses have been replaced by the mayor by new ones. -> The mayor and the new ones replaced all the old school buses.

Solution 2:

"With" would work better to here in order to avoid the repetition of "by." "All of the old school buses have been replaced by the mayor by new ones" sounds unnecessarily clunky because of that repetition.

Solution 3:

A Google Books search for "replaced with new ones by" versus "replaced by new ones by" across books and periodicals published between 1800 and 2008 found 52 unique matches for "replaced with new ones by" and 42 unique matches for "replaced by new ones by." Clearly we're talking about an extremely small pool of examples; but I was somewhat surprised that "replaced by new ones by" did as well as it did. My conclusion is that you can use either preposition before "new ones" in that syntactical setting and not be judged to be badly out of step with the multitude.

Meanwhile, an Ngram chart of "replaced by new ones" (the blue line) versus "replaced with new ones" (the red line) versus "replaced with new ones by" (the green line) and "replaced by new ones by" (the yellow line)—to give a sense of the relatively negligible presence in the Google Books database of the latter two wordings—over the same time period shows a decided preference for "replaced by new ones":

Given that the quoted phrase entails a passive construction, this result appears to be the one you expected. Nevertheless, "replaced with new ones" receives a fairly strong level of support in those instances, particularly in works published in the past century or so. On the strength of these results, I wouldn't go so far as to say that "replaced by new ones" is the only acceptable way to express (in passive voice) the idea of replacing something old by/with something new.