P.S: All the UTXOs used were confirmed, so it's not about pending parent transactions.
That's only an issue for CPFP's effectiveness.
But since you're using RBF, the problem is with your transaction's children.
If there are already a lot of unconfirmed transactions that spent your transaction's output (
and their outputs' output, or even just one),
those will all be evicted from your server's and most node's mempool, so to prevent such network spam attack vector, RBF's rule will require you to include their total transaction fee to your replacement transaction.
And that's a problem with how Electrum computes the new required transaction fee as it can only take in account of your transaction's txfee.
You may manually compute it by checking all of its children transaction's "
absolute fee" (
not fee rate)
Or the lazy method of just going for small additions until you reach the point that it works.