I've had sure footing on a cavern dweller/beastmaster felar for approximately 15 game hours. Not once in that time has the skill improved, even when the learning bonus was in effect and I fought multiple bashing NPC's in caves. I improved/mastered other similar automatic skills (including shadowstride) that I learned much later.

Since there's no visible indication when it works, I can't tell if it's even firing but there has yet to be a situation where I knew it had worked (i.e. a bash where I wasn't lagged).

Seems fine on my end.