Then your transaction clearly looked like spam to the client.  This most likely means your transaction's inputs were quite large in number, ie Bitcoin was pulling from a *ton* of very small inputs.  The fee stuff only ever shows up for people dealing with very small amounts, sending transactions very quickly after receiving the coins which will be used as txins, or sending large transactions, either many txins or many txouts.  You fall in the last case, that doesn't mean that transactions often see the minimum fee, in fact a minimum fee of 0.03 means your transaction was *massive*.