I think you're missing an important point of Mike's: separate chains will have different difficulties.

If you set up Bittimestamp to generate a block on average once per minute, one will be generated once per minute, regardless of Bitcoin's difficulty. This is because for every hash that wins a Bitcoin block, millions are thrown away as "not sufficiently difficult". However, any one of those hashes (or many of them) are sufficiently difficult for the Bittimestamp chain, since there are potentially fewer miners computing for that chain.

So you can put BitDNS (and whatever other alternate non monetary block chains emerge) in the main Bitcoin block chain, but that forces everyone to process and store DNS data. Or you can come up with a robust and extendable way for any and all chains to be mined simultaneously.