One possible way I can see Toady doing it is to have 2 diffrent mining designations, mine stone block and mine passageway. Mine passageway would be significantly faster and will always return 'regular' stone, mine stone block takes longer but has a chance, depending on the skill of the miner, to return a stone block instead. It would then be changed so that all furnature has to be made from stone blocks, and 'regular' stone can only be used for constructions (think cobblestone). Due to the smashed-up-into-little-peices nature of 'regular' stone, it would need to be transported by wheelbarrow/minecart, whereas stone blocks could be either transported or hauled. Also, 'regular' stone would make movement through a tile slower (think clutter in a workshop).
I think this would be the most realistic way to handle it, seeing as I've never come across a cobblestone table, nor could I invisage one, it would have to be cut from a single block of stone.
This would also prompt things like stone quarrys later on, seeing as you would probably be more concerned with digging your fortress out quickly at the start, but then need stone to make your furnature. The extra effort in all this (transporting cobblestone and slow mining of stone blocks) would also help to make other matterial furnature more appealing (ie.wood), seeing as it is hardly used at current.
ore veins would obviously be an exception to this and would act as they do now for either designation, except the ore itself wouldn't be useable for furnature (iron-ore-cobblestone tables?).
As an extension of this system, he could also make all items on the floor cause increasing levels of clutter, although for this, DF would need to take into account the volume each item occupies, which would be a major overhaul (but is probably enevitable at some point anyway).
tl;dr: Regular stone replaced by cobblestone only useable in construtions and slows movement when on floor. Option to mine stone blocks instead but takes longer and can fail (resulting in cobblestone).