InsufficientMaxFee / max_fee_from_policies: 0

We have released a new fuel core version 0.31.0, you can read about it here. Can you try updating the toolchain to the latest and see how how it goes?