(nb: Gavin is on vacation at the moment, I post this now just to give food
for thought over the holidays).

I patched my bitcoind to use a modified version of Gavin's fee estimation
framework. Here is what it's currently estimating. This shows number of
samples taken for fee-paying transactions and free transactions (where
confirmation requires priority), along with the median fee paid and then
the 10th percentile fee paid, and median priority for the free transactions
(no 10th percentile there). -1 means missing data, of course. Max 1000
samples.

2013-12-28 18:34:42 estimates: for confirming within 0 blocks based on
1000/383 samples, fee=38759.7/16155.1 (10%) per kilobyte, prio=8.41811e+08
2013-12-28 18:34:42 estimates: for confirming within 1 blocks based on
1000/202 samples, fee=26738/16155.1 (10%) per kilobyte, prio=2.91473e+08
2013-12-28 18:34:42 estimates: for confirming within 2 blocks based on
298/115 samples, fee=22831.1/10341.3 (10%) per kilobyte, prio=3.18117e+08
2013-12-28 18:34:42 estimates: for confirming within 3 blocks based on
115/88 samples, fee=22831.1/8810.57 (10%) per kilobyte, prio=2.53442e+08
2013-12-28 18:34:42 estimates: for confirming within 4 blocks based on
17/26 samples, fee=14992.5/2759.38 (10%) per kilobyte, prio=2.99917e+08
2013-12-28 18:34:42 estimates: for confirming within 5 blocks based on 1/12
samples, fee=7468.26/7468.26 (10%) per kilobyte, prio=4.12797e+08
2013-12-28 18:34:42 estimates: for confirming within 6 blocks based on 1/9
samples, fee=8071.03/8071.03 (10%) per kilobyte, prio=1.32007e+08
2013-12-28 18:34:42 estimates: for confirming within 7 blocks based on 5/22
samples, fee=3018.41/1.91939 (10%) per kilobyte, prio=9.60733e+07
2013-12-28 18:34:42 estimates: for confirming within 8 blocks based on 0/9
samples, fee=-1/-1 (10%) per kilobyte, prio=1.22123e+08
2013-12-28 18:34:42 estimates: for confirming within 9 blocks based on 0/8
samples, fee=-1/-1 (10%) per kilobyte, prio=6.42686e+07
2013-12-28 18:34:42 estimates: for confirming within 10 blocks based on 0/3
samples, fee=-1/-1 (10%) per kilobyte, prio=6.72846e+06
2013-12-28 18:34:42 estimates: for confirming within 11 blocks based on 0/9
samples, fee=-1/-1 (10%) per kilobyte, prio=5.42872e+08
2013-12-28 18:34:42 estimates: for confirming within 12 blocks based on 0/1
samples, fee=-1/-1 (10%) per kilobyte, prio=1.13419e+07
2013-12-28 18:34:42 estimates: for confirming within 13 blocks based on 0/3
samples, fee=-1/-1 (10%) per kilobyte, prio=4.57343e+08
2013-12-28 18:34:42 estimates: for confirming within 18 blocks based on 0/2
samples, fee=-1/-1 (10%) per kilobyte, prio=5.51321e+08
2013-12-28 18:34:42 estimates: for confirming within 20 blocks based on 0/3
samples, fee=-1/-1 (10%) per kilobyte, prio=4.41654e+08
2013-12-28 18:34:42 estimates: for confirming within 22 blocks based on 0/4
samples, fee=-1/-1 (10%) per kilobyte, prio=4.04413e+08
2013-12-28 18:34:42 estimates: for confirming within 23 blocks based on 0/4
samples, fee=-1/-1 (10%) per kilobyte, prio=5.02467e+08
2013-12-28 18:34:42 estimates: for confirming within 24 blocks based on 0/1
samples, fee=-1/-1 (10%) per kilobyte, prio=2.76975e+08
2013-12-28 18:34:42 estimates: for confirming within 25 blocks based on 0/1
samples, fee=-1/-1 (10%) per kilobyte, prio=2.90481e+08
2013-12-28 18:34:42 estimates: for confirming within 27 blocks based on 0/3
samples, fee=-1/-1 (10%) per kilobyte, prio=3.49409e+08
2013-12-28 18:34:42 estimates: for confirming within 28 blocks based on 0/1
samples, fee=-1/-1 (10%) per kilobyte, prio=1.35682e+09
2013-12-28 18:34:42 estimates: for confirming within 31 blocks based on 0/2
samples, fee=-1/-1 (10%) per kilobyte, prio=2.17966e+08
2013-12-28 18:34:42 estimates: for confirming within 36 blocks based on 1/0
samples, fee=8103.73/8103.73 (10%) per kilobyte, prio=-1
2013-12-28 18:34:42 estimates: for confirming within 47 blocks based on 1/0
samples, fee=608.273/608.273 (10%) per kilobyte, prio=-1
2013-12-28 18:34:42 estimates: for confirming within 48 blocks based on 1/0
samples, fee=11415.5/11415.5 (10%) per kilobyte, prio=-1
2013-12-28 18:34:42 estimates: for confirming within 51 blocks based on 0/1
samples, fee=-1/-1 (10%) per kilobyte, prio=1.01951e+09
2013-12-28 18:34:42 estimates: for confirming within 55 blocks based on 1/0
samples, fee=3891.05/3891.05 (10%) per kilobyte, prio=-1