I have tried 2 pets now and neither of them have moved past loyalty level 1 despite being well fed and each levelling once, the first pet actually started with negative training points. I don't remember it taking this long to gain loyalty.
I did receive 2 of the Hunter 'find pet' level 10 quests, could this have something to do with it?