I was going to send a transaction but the it was too large and my client (0.7.0) wanted me to pay a fee. However, I was not fully synchronized with the blockchain yet. The client knew this. I waited a few more blocks and sent the transaction without having to pay the fee.
The message asking me to pay a fee didn't mention the blockchain not being synchronized. Users who are unaware of how fees are calculated could have paid an unnecessary fee to the network had they accepted prior to the client knowing that there was a way to send coins w/o the fee. Perhaps the error message could be modified to reflect this?
Edit: Opened an issue here
https://github.com/bitcoin/bitcoin/issues/1858
