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.
All the earlier reports were resolved as "Working As Intended". Just like this one is now.