I'm sorry you're disappointed with us...

Ever since the increasingly full blocks we've started working on better fee estimations (both to avoid too high and too low fees), but this isn't an exact science and there's a few configuration variables we need to tweak on our algorithm to get to the perfect spot.

The key is to estimate the 'perfect' fee/kb based on the previous blocks found, the value of your transaction has nothing to do with that.

I agree, we were off on this one, the fee/kb should have been ~0.00032493 BTC/kb which should have put the fee for this transaction around 0.000121199 BTC.
Instead we estimated 0.00012 BTC/kb and the resulting fee was 0.00003810 BTC.

I've tweaked a few of the configuration variables to make sure that in the future in this scenario it will use a higher fee, while still using lower fees for when blocks are less full.

Regards,

Ruben
CTO, Blocktrail