Increase transaction fee with Bitcoin Core client fails because of no change output. Why?
BIP125 RBF (Replace-by-fee) transactions in bitcoin-core 0.15.0.1 appear to require a change address with a balance in order to facilitate a future RBF-based fee increase.  

By way of an example, consider the following transaction:

Input  - 1.00000 BTC
Output - 0.99998 BTC
Fee    - 0.00001 BTC
Change - 0.00001 BTC


Assume the fee is too low.  Now, we want to increase the fee for the transaction, so the RBF replaces the prior transaction with one like:

Input  - 1.00000 BTC
Output - 0.99998 BTC
Fee    - 0.00002 BTC
Change - 0.00000 BTC


Now the fee is enough that the transaction is confirmed.

Without "change" present in the first transaction, there is no source for the increased fee.  RBF could be implemented such that the output is reduced to allow for a greater fee; I'm not sure why that is not supported.  Line 2928 of the wallet.cpp source code in the bitcoin-core github repository states:

break; // Done, able to increase fee from change


The way around this problem for a transaction that has RBF enabled, but has no change address is to follow the directions contained in one of the answers in the canonical "transaction not getting confirmed" question.  I experienced the exact issue last week and was able to successfully recover using the -zapwallettxes option in the bitcoin-core wallet CLI.