The Bug
The terrain generation in the Mesa Bryce biome has a lot of stone and coal above ground, spoiling the look of the biome. Generation was fine up to 1.9.4. This is caused by the change made in 16w20a that hardened clay and stained clay no longer generate more than 15 blocks deep, if the mesa is more than 15 blocks above sea level.

Steps to reproduce:
In versions 1.9.4 and 16w20a respectively:
Generate new creative world, seed 4031384495743822299
/tp @p 925 110 -200 140 19
Screenshots for newly generated worlds attached.

Fix from Neko: (Based off of Minecraft 1.10, MCP 9.30)

    public void genTerrainBlocks(World worldIn, Random rand, ChunkPrimer chunkPrimerIn, int x, int z, double noiseVal)
    {
        for (int j1 = 255; j1 >= 0; --j1)
        {
            //i1 is sea level
            //was previously "else if (i1 < 15)"
            else if ((i1 < 15 && !this.brycePillars) || this.brycePillars)
            {
		
            }
        }
    }

This fix will let Mesa Bryce generate like it did in 1.7-1.9.4 while regular Mesa's will only generate 15 blocks deep if above sea level.