Again, while this is true for naga that were born before the War of the Ancients and those indoctrinated, I doubt all new naga were indoctrinated.
Do you remember the quest on the goblin starting area (the island they crash-land on) where you're sent to kidnap naga babies? And there's countless numbers of them! Now imagine that after the War of the Ancients, how many loyal Highbourne to Azshara were there left? The rebels were already in the capital. A few thousands? Sure. A million loyal subjects to Azshara? I doubt that a million could fit in her palace and on the walls of it. So most of the rest of the naga were born after. They never experienced the War of the Ancients. They are like north koreans, teached from children to love the supreme leader and to hate the landwalkers. Yet I doubt all believe what they're told. In the end, many did visit the land, so they might have seen south kore... I mean the land, it's not that bad and the races on it are just trying to survive too. There could be rebel factions around there, in the end, was not Vashj and her naga a rebel faction? They left their queen to follow Illidan. Even the naga underwater loyal to Azhara make it clear they were disappointed with her choice during the battlemaiden questline.
What if there's more rebel forces, only some fighting to overthrow their dictator? To whom would they go, if not those that their dictator claimed to be their most hated enemies. And who are their most hated enemies according to Azshara? Night elves.
But now, you might say, why would night elves accept them? For the same reason they accepted erredar to join the Alliance. Oh wait, those weren't erredar, they were draenei, good "erredar". And night elves accepted them. So what's stopping them from accepting a faction of good naga? (good is a relative term, they won't be as good as draenei, I hope not at least, but they won't be those guys trying to end the world, so, as such, won't be evil).