See this transaction here: http://blockexplorer.com/t/37LGcZAis7 in this block: http://blockexplorer.com/b/119132
The transaction was 0.225 kB, one input, one output and total block size was 4.07 kB and I was told that it needed a 0.01 BTC transaction fee. WTF?
Low-priority transactions (where priority is determined by bitcoin amount and age of the inputs) require a fee. You sent a very-small (0.03 BTC) transaction that came from a few-hours-old transaction.
That is by design, to discourage sending lots of very-small transactions (also known as "penny flooding").
The pop-up display when you want to send such low priority transaction, however, is very misleading. It says "This is an oversized transaction that requires a transaction fee". I spent quite some time (and had to look into the source) to understand why such small size transaction is said to be oversized. The best would be to have different text for low-priority transactions are at least add "or low priority" to this general message.
I changed the message to:
This transaction requires a transaction fee of at least 0.0N because of its amount, complexity, or use of recently received funds
... and I'll recompile to pick up this change for the final 0.3.21 release.