For reference this is on the rinkeby testnet blockchain. I have tried creating a totally new wallet from scratch, increased the gas fees, and nothing has worked. What do I do?
[ethjs-query] while formatting outputs from RPC ‘{“value”:{“code”:-32603}}’
Hello! Welcome to the MetaMask community )
Can you show your blockchain connection configuration?
What provider are you using?
I agree, this may be due to the network itself, which is often testnets, try to make a transaction later, in the evening or in the morning, then the networks are less loaded
Hey @hamson, welcome to the MetaMask community! 
This article on our Knowledge Base may help you:
If you haven’t already, try also increasing the priority fee
Nft support MetaMask easy way