Cancelling Transaction from pre EIP-1559

Hi,

When trying to cancel a transaction that was submitted pre EIP-1559 I always get this error: Transaction failed! Error: … replacement transaction underpriced …

I am trying to cancel a transaction by sending another one to myself with the same nonce, and giving it a fee that is well over that in the original transaction.

Anyone else had issues with cancelling old transactions?