Then this problem has nothing to do with the gas, I believe it the Ethereum network congestion because it seems like the transaction was not available in the mempool. Restart your metamask, cancel the transaction and create another transaction that should fix the problem.