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.