I apologize if this is a duplicate. I saw bugs regarding this for previous versions that all said resolved, but this is still an issue in the 1.9 snapshots and there were none reported for these versions.
Shovel has the following enchantments
Unbreaking II
Efficiency IV
Fortune III
This shovel can get me dirt and sand just fine, but when I try to use it on gravel all I get is flint. From previous bug reports this looks to be caused by an issue with the Fortune enchantment.
Environment
Windows 10 Professional
Java 1.8.0_25 64-bit
CPU: 8x AMD FX-8350 8-core
GPU: Nvidia GeForce GTX 780
RAM: 16GB (Minecraft gets 6)
Running on a multiplayer server which has 4GB of RAM on an amplified world. (seed: 1409495973539796894)
All the earlier reports were resolved as "Working As Intended". Just like this one is now.