Don't just any axes work to make a shelter? Maybe the issue is your building skill. Here's the Shelter's recipe:
.Shelter. [effort:2] [phys:arms,stance,one-armed] -S- *BUILDING* /30/ %30%
{Cutting weapon} <Axe>
{Slender trunk} (3) [remove] [ground]
{Spruce twig} (20) [remove] [ground]