Since you can have more than one pet of the same kind now in the new pet journal, Blizzard has set a limit of 500 total and 3 of any one kind.
http://www.warcraftpets.com/news/patch-504-is-here/
Players are allowed to temporarily go over that limit right now, since all your characters' pets are combining in the new pet journal for the first time (although even now there is still a limit according to blue posts, 1500 pets I think). When MoP hits we'll be getting a function to cage some pets and sell them, for now all you can do to get under the limits is to release pets.
You can't learn any pets unless you are under 500 total (I don't know if you're able to learn a particular pet if you're over 3 for that pet). But I don't think it's intentional that you actually lose the pet, so you can put in a ticket for that.