it was not because of a new wallet instead it was because of your transaction total was not sufficient enough(or because of bug maybe? who knows).
try to lower your transaction or sending it partially, it might help you to do this transaction.
so far it works and a lot of people use this method to fix this problem