In the recent 1.8 snapshots, Mojang made cobblestone generate under gravel paths to prevent it falling into caves. This doesn't fix the problem. I found a village in a world and I saw that the supposed "cobblestone" under the path just generated at the bottom of the cave below the gravel.