user1843: I'm attempting a test transaction of an amount less than 0.0015 BTC with my transaction fee set to 0 BTC, yet I'm getting this message: 

The total exceeds your balance when the 0.0015 BTC transaction fee is
  included.

The transaction fee should be free, right? Why would this happen?

user3439: For certain transactions, particularly transactions that have a large number of inputs, or relatively new inputs, the Satoshi client will not let you initiate a transaction without a 0.5mBTC fee. Essentially it tries to prevent you from initiating transactions that will have problems getting forwarded/approved. If you have less than 0.5mBTC is should warn you about this after clicking send.
Note: this is just the way things are. I don't particularly like it that way, I wish there was an advanced option that let you override it, but as far as I know there isn't one. And I do understand the rationale, as we get enough posts as it is on this forum regarding people frustrated with their no fee transactions not getting confirmed.

user3292: Bitcoin-Qt enforces the reference implementation:
A transaction will be sent without fees if these conditions are met

It is smaller than 10 thousand bytes.
All outputs are 0.01 BTC or larger.
Its priority is large enough

Otherwise, the reference implementation will round up the transaction size to the nearest thousand bytes and then add a fee of 0.0005 BTC per thousand bytes. Users may override the default 0.0005 BTC/kb fee setting, but cannot control transaction fees for each transaction. Bitcoin-Qt does prompt the user to accept the fee before the transaction is sent (they may cancel the transaction if they are not willing to pay the fee).   
Source

1843: <p>I'm attempting a test transaction of an amount less than 0.0015 BTC with my transaction fee set to 0 BTC, yet I'm getting this message: </p>

<blockquote>
  <p>The total exceeds your balance when the 0.0015 BTC transaction fee is
  included.</p>
</blockquote>

<p>The transaction fee should be free, right? Why would this happen?</p>
 3439: <p>For certain transactions, particularly transactions that have a large number of inputs, or relatively new inputs, the Satoshi client will not let you initiate a transaction without a 0.5mBTC fee. Essentially it tries to prevent you from initiating transactions that will have problems getting forwarded/approved. If you have less than 0.5mBTC is should warn you about this after clicking send.</p>

<p>Note: this is just the way things are. I don't particularly like it that way, I wish there was an advanced option that let you override it, but as far as I know there isn't one. And I do understand the rationale, as we get enough posts as it is on this forum regarding people frustrated with their no fee transactions not getting confirmed.</p>
 3292: <p>Bitcoin-Qt enforces the reference implementation:</p>

<p>A transaction will be sent without fees if these conditions are met</p>

<ul>
<li>It is smaller than 10 thousand bytes.</li>
<li>All outputs are 0.01 BTC or larger.</li>
<li>Its priority is large enough</li>
</ul>

<p>Otherwise, the reference implementation will round up the transaction size to the nearest thousand bytes and then add a fee of 0.0005 BTC per thousand bytes. Users may override the default 0.0005 BTC/kb fee setting, but cannot control transaction fees for each transaction. Bitcoin-Qt does prompt the user to accept the fee before the transaction is sent (they may cancel the transaction if they are not willing to pay the fee).   </p>

<p><a href="https://en.bitcoin.it/wiki/Transaction_fees#Reference_Implementation">Source</a></p>
