This issue has been ongoing for at least a couple versions now, as I mentioned in the environment.

Started a new server for testing purposes and funsies (small, just 3 players) using the then-latest snapshot 15w51b, and we noticed that leads are not functional, though at the time we didn't really figure out what was wrong, we just said 'whatever, snapshot' and moved on. But then when 16w02a came out today, I noticed a bugfix labeled that chickens and zombies wouldn't go up stairs (something I had not noticed, to be fair) and wondered if it was related.

Long story short: Probably not related. But!

It allowed me to realize what the problem with leads was: Animals will not follow you up 1 block steps. They won't jump!

If you lead the animal DOWN or on FLAT surfaces, there is no issue. But UP - no go.

Definitely a big problem as it basically makes leads near-worthless!

Hopefully this one is an easy fix that you can roll out ASAP!

Thanks guys!