LVL 40 horse

Hi, i had a problem with training my lvl 40 horse. It appears red for me the power so i cant learn it. so i went where all the blood elfs learn their mounts and they dont give me any train. im not sure if i need a quest or something, cause im 41 and i cant use my pala horse or a normal mount cause i cant train. is there any quest? or something or is just my character that is bugged? :((

What is the name of the NPC you spoke to for the riding training?

you need to learn the 100% riding skill first, then go to the paladin trainer and learn the new horse skill