This issue is always been happened to me that's why I switch to electrum for android, if ever you still wanted to use mycelium wait for their nwe update until they fix the issue.
Has this issue been happening to you recently or have you experienced it previously? I have used Mycellium for years and this is the first time I am having issues with transactions failing. This is my first time trying to use the wallet after their big modular update.
I did try electrum but it doesn't have the features I need.