Addendum:
Please do not interpret - as many have - my points as advocating against letting a fee market ever develop(!).
Fees are useful against DoS, increasing cost of attack etc. Further, continuing the artificially-low fee policy ad infinitum is unsustainable and constitutes a moral hazard.
Examine from the user's point of view. If you want to develop a fee market, think it through in the context of user expectation/experience - which translates to how software is written and users behave, the context of market disruption, and the context of further block size increases.
Transition to a new economic policy should be planned. It should give users and markets time to adjust.
It is grossly irresponsible to simply drop users into a new economic policy with no warning and no preparation.