This server might be using BIp25 rules which is the fee to be payed for replacement of transactions must be higher than the total fees of all transactions to be replaced in the mempool.
Right, but to be more accurate:
The total fee you pay for the replacement transaction must be higher than the the sum of the total fees paid for the transactions that will be evicted from the mempool after the replacment and the minimum fee required for its own bandwidth.
Electrum will increase the fee by default. For example, if you set the fee to 1 sat/vbyte when you broadcasted the transaction, you will see 2 sat/vbyte when you want to bump the fee.
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.