When you ask the blacksmith for a shovel, he says to take one from the box that you get other tools from, but there is no option to get the shovel like there was for the saw or axe.
This issue should now be resolved after the recent patch where we reworked some of the quests on newbie island. Please let us know if the problem still persists.