As someone with a serious soy allergy, I am not a fan of this either.
They replaced my egg with knowledge
(yes I know tahu can mean both tofu and ''to know'')
I came here to comment on that. While they are spelled the same, knowledge is pronounced "tah-u" while tofu is "ta-hu". I wish the speach processor in this app would get the pronunciation correct.
Should it be exchange not change? They exchanged my egg with tofu. Rejected. They change my egg into tofu is also ok as a magic.
The English doesn't sound quite right to me. With "for" instead of "with" would be one way to improve it.
in the context of this sentence, neither 'change' nor 'switch' are quite right.
as mentioned in the posts already; 'replace', 'exchange' or 'swap' would provide a more natural english translation. also, as hippietrail has noted, in english 'for' needs to be an accepted preposition, depending on the verb:
'they replaced my egg/s with tofu'
'they exchanged my egg/s for tofu'
'they swapped my egg/s for tofu'