I can't extrude on the z axis
Wow. This is a curious one. I think this is what's going on..

You're extruding edges, along their median (actually mean) Normal, which is to say the mean normal of their vertices. In the first extrusion, all the vertex normals have a -Z component, the X's and Y's cancel, so the mean normal is -Z. In the second extrusion, none of the vertex normals have a Z component, the other components cancel, and so the Normal is 0. Blender seems to gives an arbitrary vector for this?
TL;DR
Fill the hole and  extrude a face, which has a normal, of use the XYZ setting for the tool.