I wouldnt suggest any fixed fee. The transaction may also be unusually large (in byte) for Erkallys which might be why they didnt have this problem before. You either have a wallet that can make a good suggestion or you have to rely on 3rd party estimates from e.g. 21.co.