Till yesterday, I was able to deploy. But since morning, I am stuck with this issue.
I restarted browser few times, cleared all cache, even cleared MetaMask user activity but still the same issue.
I am sure I have enough funds to pay for the Tx.
It is now working for me since morning, not sure what was the issue.
Last night I cleared all cache, closed MetaMask. When I tried today morning, it started working for me.