Transaction fee required by bitcoin-cli keeps increasing as I increase the fee I am using bitcoin-0.13.0 and trying to send 0.035 btc to someone.

./bitcoin-cli [auth] sendtoaddress XXX 0.035


Error: This transaction requires a transaction fee of at least 0.00150835 because of its amount, complexity, or use of recently received funds!

Then I try to set the fee:

./bitcoin-cli [auth] settxfee 0.00150835


=> true

... and try to send again:

./bitcoin-cli [auth] sendtoaddress XXX 0.035


Error: This transaction requires a transaction fee of at least 0.00187149 because of its amount, complexity, or use of recently received funds!

.. and this keeps going on and on and on with various random values being output as required transaction fees regardless how many times I set the tx fee.

There have been no transactions in my wallet for some 4+ days.

I thought the transaction fees were optional? now this is becoming more and more like my bank charging a fee on each wire?

What am I doing wrong?
The problem with sendtoaddress is that the transaction size isn't known in advance.  It may be that by adding a fee, you are needing to include a new input in the transaction, but inputs are the largest and therefore the most expensive part of the transaction, so that makes it still more expensive.  That would be most likely if you have a lot of addresses with small amounts in them.

Also, settxfee sets the fee per KB, but from a quick review of the code, that message seems to be printing an absolute amount rather than a rate per KB.

You may want to adjust the settings described here:

https://bitcoin.org/en/release/v0.12.0#wallet-transaction-fees

For complete control, you can use createrawtransaction/fundrawtransaction, or use an external system (e.g., coinb.in) to create the transaction and just sign it using your core wallet.