It's not very well thought out.
The main problem is it calculates fees based purely on blockchain data, so if miners ever accept transactions for reasons other than fees, or because of some contract to mine transactions for someone else, the estimates get pushed down and your transactions will get stuck. If a transaction does get stuck, there's nothing you can do about it other than wait - no different from now.
There are already miners with such contracts, Eligius for example, and the practice is likely to become more widespread in the future because the payment protocol is designed to allow the shifting of the burden of mining a transaction to the merchant. The only way the merchant can get a transaction confirmed if the customer put a too-low fee is to either respend it, making use of Luke-Jr's child-pays-for-parent code, (not yet included in the reference client) or by using a out-of-band transaction mining contract. The latter is cheaper because you don't have to pay for a wasteful second transaction.
The other issue is that fee estimation can only be done by full clients; the SPV clients that more and more people are using don't have the blockchain data or mempool so they can't make good fee estimates. Gavin's solution is to make full nodes provide SPV clients with estimation services, but there's no way for the client to know if the node is lying - it gives miners incentives to setup lots of nodes that lie about fees, saying they are higher than they really are, or griefers incentives to do the opposite and get people's transactions stuck. Bitcoin is supposed to be as zero-trust as possible...
There are better solutions, the main one is transaction replacement. Basically if your first transaction isn't getting mined, you broadcast a second one that spends at least one of the same inputs (so both can't be mined at once) and pays every output that the first did, plus another change output. (so zeroconf transactions are still "safe") This would work best if combined with
proof-of-propagation, which gives you cryptographic proof that your transaction actually got to miners, although that doesn't have to be implemented immediately.
The main disadvantage with transaction replacement is that it will confuse some wallet software, but that same wallet software can get confused by accidental double-spends, transaction malleability, etc. We're better off if people in the ecosystem write robust software frankly rather than making assumptions that aren't actually true.
Interestingly part of Gavins proposal is to make transactions expire from mempool's relatively quickly, and in that case then yeah, just like in replacement the wallet would rebroadcast a different version with a higher fee! So you still need to implement changing transactions, and you also still need to fix wallets so they handle replacements. Only in his version you have to wait until the transaction expires, which is problematic because you've got stuff like misguided people rebroadcasting transactions that they don't own, preventing the expiration from happening. (making expiration permanent is ugly too - what if you're trying to get a transaction paying you mined, and can't change it?)
Fee estimation with replacement is fine though, as it lets you replace transactions in the event that the estimate was too low. This helps remove some of the incentive for griefers to play games lying to SPV clients, and it lets people be more aggressive in their bargaining with miners by allowing people willing to wait a little bit the ability to make an initial low-ball bid, and raise it if needed.
tl;dr: Why would you want to be at an auction for something you needed where you got exactly one chance and one chance only to make a bid? There's nothing wrong with making an initial estimate for your first bid to save time, but the bottom line is you're going to be able to get a better deal if you can make a low-ball bid first, raising your bid only if required.
