How do you choose the correct fee with Bitcoin Core?
Bitcoin Core has updated their fee estimation logic several times in the past few years, another patch coming up shortly in Bitcoin Core 0.15.0. If you aren't running a current version of Bitcoin Core, you should first update your software to the most recent version.

If the problem occurred with a recent version of Bitcoin Core, you should consider checking different resources on the web to get a feeling for the current fee level on the network in order to sanity-check the fee level suggested by Bitcoin Core during the transaction generation process.

Some such sites are:


https://btc.com/stats/unconfirmed-tx
https://bitcoinfees.github.io/
https://bitcoinfees.21.co/


Another option would be to use the RBF feature, although this is currently only available for crafting transactions via commandline. A pullrequest to support it in the GUI is in the makings, I think that Bitcoin Knots (Luke Dashjr's client) already supports it in the GUI.