A lot of us have been running into a bug where we have bought Battle Pet Training on a character, but some other/new characters do not have it trained in their spell book.
Long story short, it appears to strike if you create a character and then log them out before they hit level 5 and "learn" the Battle Pet Training Ability.
This seems to be due to a fact that you actually have it learned when you first create your character and log them into the world. BUT, if you log them out before level 5 and then log them back in, they lose knowing it. Once they hit level 5, they do not seem to relearn it., though they should.
I have posted more info on the bug forums, and am exchanging tweets with Cory Stockton, to try to get this bug moved along. Here's a link to my bug forum post on the WoW forums.