I had this happen to me recently. I use a mod called "PatBattle Teams"
I was able to "fix" the teams by using the "Reconstruct Teams" button.
This button can be found in the mod options. I had to dig around a bit to get there, but here's how I got there:
1) Log in to any character
2) Press Escape
3) Click the Interfaces button
4) Click the AddOns tab on the left.
5) Click on "PetBattle Teams" to bring up the UI.
This dud pretty good job of fixing the teams, but there were a couple things I noticed:
!) On teams where you only had two pets and leave slot open for the leveling pet, it seemingly inserted a random pet into the empty pet slot.
2) On some of my teams, it reconstructed the team with the correct pets, but sometimes it would use the wrong breed of the pet.
Still, the end result was much better then loosing everything.