Electrum increases the fee rate of the replacement transaction by default, but that may be insufficient. As suggested by the error message, OP should be able to broadcast the transaction simply by increasing the fee.
Yes, I know the fee may not be enough, that is the reason I included that the fee can then be customized. I increased the fee but it does not work, and this is not the first time that I noticed this. Even if the fee is increased excessively, the same error is the there until it is changed to preserve payment.
You may manually compute it by checking all of its children transaction's "absolute fee" (not fee rate, use a Blockexporer)
Or the lazy method of just going for small additions until you reach the point that it works.
Did you tried it and it worked? It is not working as I tried it up to 600 sat/vbyte. Just one child transaction with 1 input and 2 outputs.