Satoshi's Client has a set fee of 0.0005 BTC, although it enables you to "choose the fee". If you choose a lower one, youll get an error message once you actually try to send a tx. Sometimes you also have to pay more, like 5 times as much as the minimum fee (0.0005), dont know if that is somehow part of change?