(Update: The client has changed the min fee from 0.0005 to 0.0001)
Yes, the Bitcoin-QT client applies a minimum fee of at least 0.0001BTC to some transactions. Quoting the wiki:
Sending
A transaction may be safely sent without fees if these conditions are met:
- It is smaller than 1,000 bytes.
- All outputs are 0.01 BTC or larger.
- Its priority is large enough (see the Technical Info section below)
Otherwise, the reference implementation will round up the transaction size to the next
thousand bytes and add a fee of 0.1 mBTC (0.0001 BTC) per thousand bytes1. As an
example, a fee of 0.1 mBTC (0.0001 BTC) would be added to a 746 byte transaction, and a
fee of 0.2 mBTC (0.0002 BTC) would be added to a 1001 byte transaction. Users may
increase the default 0.0001 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).
Note that a typical transaction is 500 bytes, so the typical transaction fee for
low-priority transactions is 0.1 mBTC (0.0001 BTC), regardless of the number of bitcoins
sent.
The "priority" mentioned is calculated based on the quantity of bitcoins and the age of the bitcoin inputs making up the transaction (ie how long since you received them). It prevents a user flooding the network by repeatedly sending bitcoins to themself.
Note that this isn't a restriction on the Bitcoin protocol itself though. More details here.
In your case, the only thing you can likely control is the ages of the bitcoins; ie waiting will help meet the third requirement.
