Everyone is stuck on a hypothetical I gave out, with the point being that, IMO, bitcoin would need to be free from any uses that might discourage its uses, otherwise, the average user may not use it.
I think jgarzik says it best.
...unless the use of bitcoin for non-currency purposes discourages currency use. Some uses of the network can act as an overall disincentive against mainstream use. If people see that miners care little for currency transactions on the bitcoin network, or all the data spam increases TX fees to annoying levels, currency users will find a new network elsewhere. If people find out law-enforcement-objectionable data such as "kiddie-pr0n.p2p DNS data" is being managed on this network, that increases the incentive for currency users to go elsewhere.
Maybe that makes some miners happy in the short term, and you happy, but I'm here for the revolutionary new type of digital cash.
And this generalized data timestamping/notary service seems like it has the distinct probability of degrading service for digital cash, if it is even remotely successful.
The truth, probably, is that bitdns will never be anything big. Heck, the guy from The Pirate Bay is making his own distributed DNS. The main client shouldn't have a transaction type specifically for DNS.