Yes, duh thats why it says 25 kills ON horseback

i found it was easiest to be sure the game logs your kills, by jumping from one horse onto the horse of a guard and assassinating him. I rode around for a long time killing foot guards from horse back to no avail.

Actually, this is an error on Ubisofts part for wording - the game means to say 'Kill 25 Horseback Guards'. To get the challenge, simply kill 25 of the mounted Guard archetype, not just anyone who gets on a horse. Also, it does NOT matter how you kill them.

Just run around the countryside with the crossbow and shoot any guard riding a horse. You don't have to be on a horse and using the hidden blade on foot doesn't count because Ezio pulls the rider off the horse before he kills them

The answer is in the question. All you have to do is only go to different guards while on a horse and kill them in any way except air assassination because then it wont count.

Since it's been a while, if you still don't have this achievement, I believe you are trying to complete a DLC achievement, meaning that even though it is on your list, you need to download the Da Vinci Disappearance in order to actually get the achievement.