The fee that matters is in BTC/bytes, meaning that it may become "exorbitant" if your money comes from too many inputs.
I didn't use many Android wallets (Core really has Andro wallet?!), so i cannot tell more exactly about it. If you post the tx ID, many people can help telling what went wrong.
I can tell that the network is rater busy these days, just check the bottom of: https://btc.com/stats/unconfirmed-tx The good days are at under 8MB mempool, now it's over 60MB.
If you are in a hurry and didn't pay big enough fee, you can post the tx ID and ask people to "accelerate" it.
Edit: I've done some more research and at least it's an "approved" wallet. https://bitcoin.org/en/wallets/mobile/android/bitcoinwallet/ Even more interesting, they say there that you can control the fees, so you must have set it too low or the default was too low.