Got it! There are a lot of potential causes for this - one of them is that you’re including a nonce number when you don’t need to, or you’re trying to use an incorrect nonce number (this doesn’t seem to be the case for you, however, since using a higher gas price pushed the transaction through). Alternatively, you may need to include
value in your request (sometimes it’s finicky).
A transaction that’s not a replacement transaction can be rejected for a few reasons, but most of the situations end up being a misunderstanding where the address you’re sending from doesn’t have the balance you expect, or perhaps you’re using a helper function that returns Wei (such as estimateGas), whereas others like getGasPrice return Gwei - that has caused confusion more than once! I would definitely suggest looking into those as easy initial checks for a fix.
Lastly, there have been bugs with geth previously that was causing nodes to be rejected even with high gas prices, so I would also advise checking the geth GitHub page to see if others are running into this issue if you’re not getting anywhere with the above options.