Welcome to pet battling. It’s a shame you ran into this. It’s always been like this - a glitchy design from the start to split Alliance and Horde chains. Once you get past Eastern Kingdoms/Kalimdor, it clears up.
Among the ideas that people have found to work, you might try flying out to Trixxy in Winterspring anyway, or taking an alt - possibly in Chromie Time - to see if they can hand in the quest to Varzok or Audrey.
Or you could leave it aside for now, go around it and continue with higher level battles, and come back to it later. I wrote a guide on this, starting here: Guide: How to get your first pet to 25